I'm not necessarily endorsing it,
but one Firewall package that works in Vista is PC Tools Free Firewall
I've been running it on a Vista Premium system and it seems OK.
I believe I mentioned it in another thread, glad to hear it's working for you, BalRocket.
Don't know where that "turn off your firewall while downloading a firewall" advice came from, but it doesn't make sense.
Sometimes, though, you can actually install or run a program from a website, in which case you are both downloading and installing it immediately thereafter. I can see where this could cause a problem if the new program would conflict with an existing one that you would normally disable or uninstall before you install the new program.
Especially in matters regarding your PCs security, I would always recommend you download and save the file, and install it later once you've got your system properly prepared for the install.