The best protection is not running as an administrator all the time. I've been doing this for months now in XP, and it's not nearly as difficult or inconvenient as everyone claims. Simply not being an administrator cuts off a massive amount of attack vectors. If your user account is limited, even if malware does get downloaded, it can't ingrain itself into your system nearly as well. It also can't do anything to vital system files, simply because you can't do anything to them either.
Even if you're running as a limited user, though, most if not all of your personal information is still out in the open. So, the second best protection is using secure software and keeping it updated. Keep your system locked down and malware won't even have a chance to download. As far as I'm concerned, once your security has been penetrated, the game is up and you may as well just start over. If you rely on malware removal software to keep your computer safe, you're doing it a great disservice.
Like Sonict said, a firewall isn't much protection against spyware or adware. Firewalls are meant strictly to prevent unwanted data from being sent or received. Simply running behind a NAT router (as is probably the case, unless you still live in the stone age and connect to the internet via dial-up) often eliminates the need for a firewall.