IMHO... the best software *network* firewall value out there right now is Kerio Winroute Firewall. Yes, it does NAT, as well as tons of other network firewall stuff. Like stateful packet inspection, protocol inspection, VPN, built-in AV (if you pay extra), all rule based for in and out. Just plain good. I've been using it at home for four years (stared using it when it was owned by another company and was called Winroute).
JFTR, I have also administered a few enterprise firewalls including Raptor (now Symantec). I still believe the best value for the $ is KWF. Check out
-Frank