One of your requirements, the need for multiple public addresses, is going to be a show stopper. Of the two most popular Linux-based free firewalls, IPCop and SmoothWall, neither allow multiple external interfaces (what these products call "red" interfaces). The commercial SmoothWall Advanced Firewall product does support multiple "red" interfaces.
But all is not lost, whilst not a Linux-based firewall, the BSD-based PFsense firewall does support multiple "red" interfaces. There are some caveats to this support. In general though, PFsense is based on the m0n0wall firewall and has a very similar Web-based, front-end configuration. It's a fast, fully-featured firewall that runs on a wide variety of hardware. It supports all of the other requirements you have listed with the only possible issue you might have being that some older hardware might not be sufficient to run PFsense.
This was first published in December 2006