Internet Connection sharing setup on Ubuntu 9.04, FireStarter, etc.
 

OK, I've been trying for a week to set up a little barebones PC to function as a router/gateway/etc. device. Right now I've got a little Linksys WRT54G2 with dd-wrt functioning as the primary router/gateway device for my office but I know our bandwidth is taxing it significantly (30M fiber pipe).

So anyway, I've got a new Intel Atom barebones PC, two NICs, and here's what I'd like to do. Very simple, but I've tried and tried and searched high and low. Any instructions I find are either 5+ years out of date, very confusing or simply don't work.

What I have:

Intel Atom barebones PC: http://tinyurl.com/d75r43
Second NIC installed
Connected to the Internet via a public IP address
About 40 computers on the "internal" side that will be DHCP/NAT'ed

The goal?

Make this box do the same thing that any $50 cable/DSL router from BestBuy will do. I don't care about WiFi (many posts I see pertain to sharing an ethernet connection via WiFi).

Would like to do this with Ubuntu 9, but have tried Fedora 11 and Debian 4 (I think 4, whatever is current).

I REALLY like how dd-wrt works, and allegedly you can install it on X86, but I attempted that with no luck either.

I've tried Firestarter but can't get the friggin' thing to "Enable DHCP" despite installing dhcpd3, or dnsmasq, etc.

Help/step-by-step instructions would be immensely beneficial. A huge THANK YOU ahead of time for any help/insight.