I recently had to look for a decent, and hopefully free (as in beer), firewall for my sister's Windows machine. Given all the threats - apyware, worms, viruses - out there that any personal computer hooked up to the wide wide web, you definitely do not want to be running naked. I mean sans firewall.
I tried out ZoneAlarm, since its one of the software firewalls I hear the most about. Its a good product but the free version does not let Internet Connection Sharing (aka NAT) through. You have to purchase the full product for that feature.
After some googling, I found about Kerio Personal Firewall which is is not feature-crippled during the first 30 days. This makes it a lot easier to evaluate in your own setup. After 30 days you lose some features - ICS, pop-up/ad/script/cookie blocking, and remote administration but if you don't need those you are free to continue using the software.
To enable ICS to get through, simply check off the 'Gateway Mode' prereference. You'll also spend the usual time training it in what traffic to let in or out. The interface for doing so is well-designed and easy to use so its not really a pain.