The following is a list of software I wish I'd known about when I first got my new Mac. Most of it is free (except for the last section). It's a personal list and biased towards my own activities (mainly technical), however, many of the items should be useful to any Mac user.
I'd also highly recommend the Missing Manual books by David Pogue.
I've marked essential items with a star.
Transmission - A Bittorrent client for responsible downloading and being a good open-source citizen.
Firefox - Safari is good, but Firefox has many plugins for extra features.
Google Notifier - Does anyone not use Gmail?
* Skype - Does anyone not use Skype?
Stuffit Expander - Essential unzipping tool (email address required).
Chicken Of The VNC - Weird name, but useful if you need to control other machines using Remote Desktop.
Cyberduck - Free GUI-based FTP client - or there's FileZilla if you prefer.
iStumbler - Helps roardwarriers with wireless woes.
Mac The Ripper - For backing up your precious DVD collection (if it's legal in your country).
Real Player (ad-free BBC version) - If you need Real Player, this BBC version has less marketing annoyances. But you may be able to avoid using it by trying VLC - see below.
Pixen - Unsophisticated doodling tool, a bit like MS Paint.
SMARTReporter - Keep an eye on your hard disk's health - was a lifesaver for me.
Text Wrangler - When the Mac's own Textedit doesn't make the grade.
* VLC - Plays nearly everything you throw at it.
Disk Inventory - Great when you start to fill your disk.
QuickSilver - When you want more from your Mac.
Little Snitch (Trial) - If you're paranoid
TinkerTool - If you're obsesive about having things just the way you like them.
Audacity - If you need to do any sound editing (You'll need the little LameLib download for MP3 manipulation)
Blender - If you're involved with 3D graphics.
CocoaWGet - If you need local access to online sites.
Flickr Uploadr - If you use Flickr (firstborn required).
The Gimp - If you're too cheap to buy Photoshop.
Seashore - A much-more-Mac-y photo editor based on The Gimp.
Google Earth - If you're an explorer kinda guy.
Jing - Capture screencasts on video and share on the web.
* 1Password - A must-have if your online security life is complicated. Buy it now.
CheckOff - Lightweight and handy to-do list.
* Microsoft Office - if you can't live with OpenOffice (no link 'coz full of Flash and music nonsense)
OmniGraffle - Great drawing program (I got a bundled copy with my first Mac)
Photoshop Elements - Online version is free, but I've not used that in anger.
TechTool Pro - if you have hardware problems.
* VMware Fusion - For when you really need a legacy Windows application.
FRIENDLY DISCLAIMER: These links were good at the time of writing, but please, always check the authenticity of anything you download from the internet. We can't be held responsible for any problems you experience as a result of using information on this site.