Zeroshell is excellent. I've also searched for a decent firewall solution and Zeroshell was by far the best free firewall that I came across. Check IPCop and PFSense as well and see if they live up to your expectations.
I setup these firewalls as VMs to test the differences, just made life a lot easier.