I have been experimenting with software firewalls for Windows Vista recently. It isn't for me (as you may know from previous posts I am still resisting Vista, at least until SP1 is released). My favourite software firewall on my XP SP2 machine is of course ZoneAlarm Pro, but it isn't Vista compatible as yet. Some has recommended Sygate, but as it now belongs to Symantec and I have no intention of going back to using Norton bloat ware after years of battling with their Internet Security Suite, I guess that rules it out.
There is a free firewall for Vista called PC Tools Firewall Plus and it is pretty handy, but the interface is less robust when compared to ZoneAlarm, but I guess this is a personal preference. I have also tried the free and acclaimed Comodo firewall on XP when I had problems with ZoneAlarm and ActiveSync. I loved it but I had to uninstall it in place for ZoneAlarm Pro (I found the solution to the ActiveSync issue) due to Comodo being accused of bundling their other free products with 'spyware' - although I have seen no evidence that it effects their firewall product (but still...). The Vista version is currently in Alpha stage, but if you require a more robust XP firewall than the free ZoneAlarm give Comodo firewall a try. But back to Vista.
Check Point recently released a Vista compatible ZoneAlarm (7.1). Right now their website has yet to be updated with the new software (download links still points to 7.0 Vista-incompatible packages), so you will have to dig around to actually download it. It works well on Vista (not mine, again I have to stress) and despite the fact that it loses OS-level firewall protection, I guess you can take comport that you are better protected than the basic built-in Vista firewall, at least against most malwares.