Eu também iria com o pfsense. É baseado no FreeBSD, mas isso não deve importar, já que você provavelmente não irá interagir muito com o próprio sistema operacional, a menos que você queira. Ele usa uma interface web agradável para configuração.
Se você precisar do Linux por alguma razão, existe um projeto chamado ipcop (www.ipcop.org) e outro chamado smoothwall (www.smoothwall.org). Eu prefiro o pfsense, por causa de mais recursos e estou mais confortável com firewall pf do que o iptables.