The only third party Internet connection sharing software for Windows I'm aware of is NAT32, which is not free in any sense of the word. (The shareware version is insufficient for your purposes.) It works great, though.
There are a couple of hacky solutions you can try though. One option is to run Linux in a virtual machine like VirtualBox and use that to share your Internet connection. Another is to use free proxy server software like Squid. If you do that, you will only be able to use HTTP and FTP from the Linux machine (SSH and most multiplayer games will not work) and you'll need to configure the proxy server in all applications that need Internet access.