I'll try to categorize this somewhat. I'll also add to it over time. All are free.
Windows Essentials - If you run Windows, you'll want these.
Firefox - Much better than IE. Very secure, compared to IE, too.
Thunderbird - If you're using Outlook/Outlook Express, try this instead. Same reason as Firefox - security.
ClamWin - Unless you have a virus scanner already, grab this - free (open source, even) virus scanner.
Ad-Aware - You can't have too many spyware/adware protections on Windows.
Spy-Bot S&D - You can't have too many spyware/adware protections on Windows.
That should cover the basics for Windows for now. This is a step on the road to security. ;)
Next, Mac apps. :) I'll just look at what's in my dock (and sys prefs) for now. :D
NeoOffice - Free office suite - a bit sluggish, but pretty good. Basically a native port of OpenOffice.org to OSX.
CyberDuck - Free FTP/SFTP client, works really well.
VLC - Media player. Handles almost anything Quicktime doesn't. Has an issue with OGM files and subtitles, but other than that, it's great.
TextWrangler - Very powerful text editor with some basic syntax highlighting.
iTerm - Much better Terminal app for OSX. Don't touch this unless you know what you're doing. ;)
Skype - VoIP software - pretty good.
MacGPG - GNU Privacy Guard for OSX - signing and encryption of e-mails, files, text, etc. Take the time to learn it well if you need encryption.
Now, some non-app things...
iScroll2 - a trackpad driver for some pre-2005 *Books, which allows for two-fingered scrolling. Very nice, if your machine is compatible.
Growl - a system notification system. Works really good. Needs plugins for apps and/or apps that support it to do anything though...
And a single website, with many plugins for Safari...
http://pimpmysafari.com Really nice plugins on there. ;)
And one website where you can quite possibly find any type of software you're looking for by searching...
SourceForge. A massive directory of open source apps for all different types of purposes and for pretty much any OS. ;)
I'll probably add more to this topic later when it's not 2 AM in the morning with only 10% battery left and no power cord nearby...