Unless you already know Linux it is probably safer to go for a firewall appliance rather than building it from scratch yourself - a quick google will get you plenty of results.

Any reason you're not looking at one of the big boys such as Cisco?

Depending on your needs you will normally require three distinct services, though they are commonly included on the same box.
  • The first is a router. In order to provide any sort of control the devices need to be on seperate subnets, otherwise they could simply talk to each other.
  • The next is the firewall. The firewall's job is to stop traffic according to your rules. It doesn't really do anything else.
  • The final part is the proxy. This is the service which will talk through the firewall. While you don't have to have a proxy it is in my experience the simplest and safest way to manage access.

The firewall and router must be on the same box. The proxy can also be integrated into the same box, could be a seperate server on your internal subnet or for the really paranoid could be on a server in a DMZ.

Being on a seperate box means that the proxy could of course be Windows based, and in a primarily Windows shop that's not a bad idea as it simplifies authentication and administration.

The Linux kernel has had routing and firewall built into the kernel for a long time, which is why it is often considered as a firewall. Especially where funds are tight you can build a very very cheap firewall. There are even a number of "firewalls on a floppy" projects around, such as this one.

There are plenty of Linux solutions ready made, some are GUI interfaces to the bog-standard kernel facilities, some are complete solutions including the OS.

There is a large list on SourceForge

One well thought of product is SmoothWall

If you need a good non-Windows proxy I can strongly recommend Squid

You should probably also think about what else you may need your firewall to do:
  • dynamic routing updates
  • failover (high availability)
  • IP masquerading (NAT)
  • statefull connections
  • caching
  • DMZ support
  • Authentication (AD / LDAP / NT)
  • VPN
  • IDS
  • integration with third party content managers / monitoring
  • Traffic shaping and/or reporting