ZoneAlarm is definitely worth trying. I was using the free version for a year and I liked it so much that I paid ZoneLabs for the Pro version. Sure it bugs you with every single program in the beginning, but if you are gonna get upset about that, well... I mean, how could your firewall possibly decide for itself which programs should or should not have access to the internet? Getting permission from the user is the safest way, if you ask me. If you don't know about whether or not you should give access to a certain executable, you deny access first, and then you have a chance to go looking on the web for that file and its function before it wreaks havoc on your (and someone else's) machine.
As for Norton Firewall, I heard a while back that it can be fooled very easily by a trojan that renames itself to a filename (such as iexplore.exe) that already has access permission. They might have fixed this problem since then, though. (I certainly hope so

) Norton is alright as a company, they make reasonably good products, but ZoneLabs are the pros in the security field, not Norton.
ZoneAlarm gets my vote.