A serious yet affordable option would be a x86 router running pfsense.
You may take a look at my configuration which can handle 1Gbps+ NAT throughput tested using iperf:
http://forum.pfsense.org/index.php/topic,45439.0.html
You may read more about pfsense, it is a well-developed router operating...