NetBSD also makes a great nat-ing router/firewall
It's not Linux, and will take a little getting used to, but it's certainly worth it.
That said, Gentoo or Debian are good choices too.. if it's not a very fast box.. Gentoo might be discouraging as it will take quite a while to compile everything from source.