I'll join in with the stuff I use on Windows (some have been mentioned by other people):
IrfanView - Multi-talented graphics viewer/partial editor.
K9 - Brilliant bayesian spam filter.
Clipomatic - Clipboard enhancer, very unobtrusive.
Startup Control Panel - Adds a new Control Panel to edit Startup programs.
eMule - my P2P of choice.
MIDI OX - Multi-purpose MIDI tool.
Opera - Web browser (now on my PC, Zaurus and phone!).
TextBath - My text file reformatter (I wrote it to reformat eBook files).
WndTabs - Adds window tabs and other nice features to Visual C++ 6.
CodeWiz - Very useful add-ins for Visual C++ 6.
Sygate Personal Firewall - Finally landed on this one after trying many others.
JPluck - Converts websites into compressed Plucker format for handheld viewing.
Media Player Classic - Superb, lean video player based on WindowsMedia Player 6.4.
Beatnik clock - Skinnable clock with Internet time sync.
Miranda IM - Modular instant messenger supporting IRC, ICQ, Jabber, MSN, AIM.
EasyCleaner - Deletes old registry entries, duplicate/temp files, and other useful things.
Shareware:
TextPad - Definitely the best text editor I've come across (besides BED on the Amiga).
An interesting site with (not necessarily free) a good software list:
The Great Software List