Actually Linux is very easy to setup for NAT and Firewall. Here is my setup. Rehat 7.1 no custom kernel
Linux box has 2 nics. ETH0 is connected to cablemodem, ETH1 is connected to my HUB.
ETH0 is running both DHCP Server on ETH1 and DHCP Client on ETH0.
For the DHCP client on ETH0 I just told it DHCP. It found my ip from my cablemodem and was all set. Could access the internet and everything from linux. One thing to note is that when I had a hostname that had to be added it wouldn't work unless I edited my ifup file and forced it to my hostname.
For DHCP server on ETH1 I just used this step by step webpage I found on the web.
http://dcfonline.sfu.ca/ying/linux/dhcpd/index.html
This webpage is for RH6.0 but works in all rehats above and even other linux distros. Just make sure you touch the leases file whereever it needs to be.
For NAT and firewall I found a sweet program called gSheild.
http://muse.linuxmafia.org/gshield.html
Just follow the directions and your set. It will setup NAT for you and also is a great firewall. DSLReports said my computer was secure. It is also very easy to use if you want to setup servers cause you just go into the conf file and set the service you want from NO to OPEN or FORWARD. You'll understand it when you see it but it is great.
Now just setup all your computers to DHCP and your set. This works great for me as my laptop I use for work is setup for DHCP and I can easily move it from work to home and still do internet stuff.
Hope this helps out. If you need to you can PM me or just reply. I would be glad to help out.
*edited to add the DHCP all computers