Should have the funds to get a decent switch, managed, and then implement a NETAPP server, or a proper bluecoat proxy server.
However, if they are that tight on a budget, spend on a good switch - to manage traffic through the proxy, ideally, get a server with a gigabit Network Interface card and a compatible gigabit switch, which will thrust bandwdith of up to 1000mbps so no one notices slow internet speeds.
In terms of proxy, you cant beat good ol'd squid.
If you REALLY must, use smoothwall - it's free and has plugins to increase it's features. You have complete access to squids cache as well.
Shove 2Gb of RAM in your server, and then, share 1Gb of it, to dynamic cache. This will have soaring speeds for commonly loaded pages.
If you don't mind messing with Unix, get slackware or FreeBSD/ Debian, etc... and install Squid and go from there. I agree Smoothwall is an easier option, but it is a tad of a middle man, it acts as a router as well, unless you dont mind that.
Get two 1000mbps gigabit cards, a switch to connect this too, and share bandwidth to rest of the switches on the network.
Internet comes in from a firewall yeh? cat5? enter this into the highspeed red zone on the smoothwall.
Out, green zone. Gigabit cable to a 12 or 24 port gigabit switch for example - netgear are low cost, otherwise Cisco.
The switch may be a gigabit UPLINK, not completely gigabit - the client ports can be 10/100 Fast Ether.
In each port, put a switch to the rest of your network. So, HR might be on switch 1, on port 1. Sales might be on switch 2 port 2. You have expansion there too, 12 or 24 ports. Add servers on this too if you wish.
Configure your smoothwall, firewall can be set to just be an extra line of defense - but keep your main firewall.
You can download smoothwall from their website, see google for the address/ I think it's smoothwall.org.
Good luck! Let us know should you need anymore help.