Well i used to use Kerio v2.15 with Avast with no probs at all other than i had to block inbound access for the mail scanner or else my pop,smpt&imapi ports were open.Version 4 of Kerio is way to buggy to use the now, it still technically a release candidate, but they dont tell U that on the site.
I been using Outpost pro v2.1 for about 6 months & find it among the best firewalls U can buy, very easy to use & also to make rules, there is a thread at the outpost forum that tells U how to secure the cfg even further.
Zonelabs i find slow & bloaty, has a habit of forgetting its rules & has so many backdoors into it, also has a habit of not loading at startup sometimes.
Tiny i did try once, but found the GUi to be hideous & it took ages for it to even refresh its info, it also not a firewall for beginners as U need to have some knowledge about how firewalls work to use it.
Primedius i never heard of before, but after looking at its homepage seems to be a custom version of 8signs firewall