I disagree with Garion. There will be holes discovered in *EVERY* firewalling system. Many of the drop in and turn on appliances are not as configurable as a full fledged firewall. OpenBSD would be a good solution, as would Linux. Yes, they both have security issues (at some point in their life anyhow), but so have PIX firewalls, so have those little LInksys dsl routers, and so will everything at one point or another. So make sure you keep up on patches and whatnot for whatever you end up using.
I personally use OpenBSD + IPF. Its tested, and I know it. I have faith in the combination of my skills and the skills of the coders of those two projects. For a work environment I would go with one of the following:
CheckPoint Firewall 1: Its not the best, its expensive, it can be gotten around if you know what you are doing. But they are a big name. Management seems to like that. High availability isnt hard to do either. It can run on Linux, Solaris, WinNT, and Nokia's version of FreeBSD.
Raptor: This seems to be a *NICE* firewall, but until their latest releases the interface was lacking. It also does some proxying. I believe this runs on WinNT and Solaris. With a little work and the right admin it can easily be gotten out through. I used to do bad things at a tech support job that used Raptor
SideWinder: This is a firewall I dont have any personal experience, but some of the features sounds *VERY* interresting. Ive also had several people recommend this to me. I believe it runs on WinNT. Probably Solaris too, but I cant be sure. I didnt look at those requirements when I read up on it. This firewall does some proxying, and one of the neat features is that it loads 1 driver and 1 tcp/ip stack per network card. There has to be some extra over-head routing information between the different tcp/ip stacks (not to mention the proxying), but it seems to be worth it.
Microsoft ISA server: Yes, I am recommending a Microsoft product. I am recommending it on a recommendation from someone I know and the fact the original poster wants to try and stick with Windows. From what I am told it is pretty good, does some nice proxy caching, but the logs/reporting is horrible. Also, it is a Microsoft product so make sure you keep up on patches!