http://firestarter.sourceforge.net
My battle with configuring NAT IP Forwarding in Fedora Core 2 finally ended with Firestarter. Its a wizard-like configuration tool written in Gnome to configure a firewall and NAT. Source code is provided! Neat. 
I remember the Internet Connection Sharing Wizard when my box was running on Mandrake. I was just clicking next, next, next and then poof! I was sharing the internet. It was quick but the downside is I didn’t know what was happening.
Firestarter on the otherhand, has configurable rules. It has a condiguration console aside from the wizard. This makes it easy for newbies to setup their ICS as well as SysAd wannabees to setup their custom firewall.
I’m currrently freeloading on office internet with a very strict firewall so sharing that internet connection will be a bit troublesome if I too use a proxy server to share internet with the rest of the computers in the house. Now, my home network is happy-dappy, linux boxes and windows like. 
Thanks go to Ealden for recommending this tool.