First, on the hardware vs. software firewall - how many more machines will you have behind the firewall? How much traffic do the machines currently process? How much traffic will they process? How freaked out are your Windows administrators going to be when they have to administer a Unix box?
A hardware firewall can be an industrial strength solution but a real one isn't cheap in terms of both initial purchase price and, depending on the experience of your staff, the maintenance. For example, do you have anybody who knows Cisco IOS? (there are plenty of providers besides Cisco - they are just one of the big ones).
Almost any PC running a Unix O/S and two NIC's can provide what you want. I personally lean towards IPF (
http://coombs.anu.edu.au/~avalon/ip-filter.html) but the Linux iptables/ipchains will work too.
Basically you have a box with two NIC's in it. The Unix box has both NAT (network address translation) and filtering. The NAT portion translates a single IP address that the internet knows you as into your internal network (some non-routable network such as 192.168.1.0/24). The filtering allows you to punch through things like port 80 (www) and 25 (smtp). Just as you can control what comes into your network you can also control what goes out. If you don't want your machines making connections to any random port (generally a good thing for server type machines) you can block that too on the firewall.
The Unix box could also host email and be a DNS relay or you could have your Windows boxes do that.