If you are still looking I would check out
http://www.xorp.org/
I just found it and am buring it now to test it out. It seems like it can be made from source or booting using a LiveCD and a floppy (easier). Seems to sound pretty good and I believe it is basd off the BSD's so it should be stable.
I have also tried these already:
Clarkconnect: Big in size. Gives you alot of other features othat than routing and NAT including: Apache webserver, PHP, Snort, and some others. It would be used as a Internet Appliance more than a dedicated firewall/router.
IPCOP: Very good as a router/firewall. Is minialistic in that you wil not have things running that could be comprosimed from an attack.
SmoothWall: Very much the same as ClarkConnect. Very easy to matin like CC, but I found CC had more features I was looking for myself.
Checked out
Coyote Linux: Fits on a floppy. Very basic.
XORP: LiveCD with floppy for config files. Going to check out now.
I am currently running a home server that just as of yesterday has routing capabilites in it nd servers up a subnet of mine with DNS, firewall and NAT. It is a install of Gentoo but almost any basic linux/BSD OS will work. Here is the tutorial at gentoo.org
http://www.gentoo.org/doc/en/home-router-howto.xml
Gentoo's Doc section also has a lot of well written HOW-TO's in it that can be adpated to any *NIX system.
If you want to learn basic Iptables just about any Distro will work you will just need Iptable's routing support in the kernel.
Eric