My two cents ...
I have a Linksys 4 port router, with the built-in NAT firewall ... the built-in NAT does nothing regarding outbound traffic ...
I run ZoneAlarm Pro on one box, and Sygate Personal on the other two. The ZA box is the one that I use for sensitive information, hence the "higher" level of protection.
IMO, a software firewall MUST be used if there is no NAT Router installed on the ADSL or Cable Modem connection, and also if you are behind a wireless NAT/router.
The basic task of a NAT router is to block incoming connection attempts. Putting it as your interface to the Internet will protect you from simple incoming connection attempts (and also unsolicited UDP).
Behind a NAT router you should see NO incoming connections, unsolicited or not, unless you start opening ports.
On a residential ADSL or cable modem, the use of a simple NAT router is probably sufficient, especially if you practice other safe computing habits. I would think as a minimum that a NAT router should be installed on any ADSL or Cable Modem connection.
If your NAT router is completely stealthed, you don't open up any ports to be visible to the Internet, and your IP address assignment is dynamic (and will change when you power cycle the modem), I would think you are OK.
However, routers are vulnerable to very clever crackers ... that's why a software firewall is used. A firewall goes beyond the simple inspection of individual packets, and actually monitors, records, and tracks each individual TCP connection (or attempted connection) to verify its validity. The software firewall is not susceptible to some of the sophisticated SYN floods, FIN probes, fragment attacks, and other tricks that can be thrown at the simple NAT router.
All my PCs plugged into the LAN side of the router are on a local private network. The IP addresses of these are set using DHCP on the router. The router is a NAT router that converts between the private internal addresses and the WAN IP address on the modem side which is on the real Internet.
For some relatively unbiased advice:
http://www.wilders.org/firewalls.htm
Simple way to test the need for a firewall ...
Go to
http://grc.com/ and run "shields up". Click through the first page and on the next page scroll down to "shields up" on the left side. Click it and run "full service port scan". When finished it will give you an option at the bottom for a summary. A pass = all stealth, no open ports, and no ping replies !