Here are some of the first free programs I put in on a fresh install of Windows.
Spybot Search and Destroy
Comodo Firewall (for XP, I use the built in software firewall in Vista)
Quick Time Alternative
There are many others, mostly related to video—like Haali Splitter, ffdshow, DVDDecrypter, AviSynth, Virtualdub, etc.