Eu sempre usei Comodo no passado e é muito bom (e gratuito). Tem vários modos dinâmicos de aprendizagem, um dos quais avisa quando qualquer novo programa tenta entrar on-line e se lembra de suas respostas.
(No entanto, eu não tentei isso já que eles mesclaram seus produtos de antivírus e firewall juntos, então eu não sei se ainda é tão bom. Eu pessoalmente não uso software antivírus)
[Edit: eu verifiquei e, aparentemente, cada um dos componentes são opcionais durante a instalação, então você pode simplesmente instalar a parte do firewall, se quiser]
A Matousec executa regularmente desafios de segurança de firewall , nos quais Comodo, Outpost e Online Armor têm todos gratuitos versões classificadas como "10+ Excelente proteção"