Good post Pooh sun tzu, I too would suggest OpenBSD. However I must disagree with you on the comment about Debian being far too old, I use debian and it works great with all my hardware and every new app I need, but saying that I wouldn`t use it as a firewall.

Back to the firewall, a firewall OS should just be a firewall, no need for fancy GUI's, or 3000 additional apps, or an overloaded kernel. So i`d go wuth OpenBSD, or failing that use Smoothwall.