I'm not joking, a small server with OpenBSD and the PF filtering engine? Has excellent performance, even on the lowest end of servers, and the config file is quite readable IMHO.
In general, go with what your organization has competencies in. When it comes to routing and security, there is no substitute for experience and good training. I see most smaller places standardize on Cisco everywhere. They do so because it limits their training / skills need to only one manufacturer, and Cisco is chosen because they have a comprehensive product portfolio and a wide support network of techs.
If the above doesn't convince you, then I would consider Juniper, Checkpoint, Cisco, or Fortinet as the leading firewall brands today (in no special order).
Note that Junipers new SRX series is based on their router JUNOS software, not their previous firewall ScreenOS. It could be a bit rough right now, but it has really good future potential.
Cisco ASA are rock solid boxes in my experience, but I would not call their configuration 'easy' or 'logical' for people without Cisco training.
I don't have much personal experience with Checkpoint and Fortinet; I have just heard them praised by good people. Thus I can't really say much more about their ease of configuration..