My "must have apps" I install on a fresh install, and when I get my new mac.
Somewhat alphabetized.
AddressBookSync (Free) - Syncs my Address Book.app with my Facebook contacts, copying Birthdays, Job Titles and current display picture to keep my Contacts up to date.
Adium (Free) - Instant Messaging. Everybody I know uses MSN, but I hate the M$ Messenger app.
Alarm Clock (Free) - Alarm clock that sits in your menu bar. Have it set to play some Atreyu on full Volume at 7pm to stop messing around and go running.
Appcleaner (Free) - Uninstaller that Apple forgot.
Appfresh (Free) - Scans your apps, and checks for updates.
Bowtie (Free) - Display album art + controls for iTunes on your desktop
Ejector (Free) - Menu bar app to eject volumes. Very nice if you're like me and don't keep any volumes on your desktop.
OnyX (Free) - System Maintenance and some little customization features.
ShoveBox (Free) - Menu bar app. Use it to sync quick notes, bookmarks and just save stuff for later. Syncs with iPhone app (not free)
Things (not Free) - To Do application. First got the iPhone app, then moved to the desktop version to keep them in sync. I plan my entire day with this app, and I love it. Currently in the middle of moving from Germany back to Canada, and this is making it so much easier to stay on track.
Transmission (Free) - Torrent client. Very minimalistic which I love.
Perian (Free) - Codec for Quicktime that plays all popular formats. <3 Quicktime.
VLC (Free) - Only use it instead of QT when I want video playlists.
Twitterrific (Free with ads) - Twitter client. Have Twitterrific Premium on iPod. <3 Twitterrific.
Apps I have installed but I left out because I don't feel them "must-haves":
Unreal Tournament 2004 - Game
Ventrillo - VoIP, used for Gaming
TrailRunner - Mapping routes for Running/Hiking
Skype - Voice Chatting
World of Warcraft - Game
WowMatrix - updating addons for WoW
Little Snitch - allow or deny certain connectioins. prevent apps from dialing home
Mactracker - Keep up to date on Macs
Microsoft Messenger - MSN messenger by M$
Handbrake - DVD ripper
Hyperspaces - Customize Spaces
iClip - Copy&Paste manager IMO.
CandyBar - Change icons. Useful for icons like Finder that can't be changed the conventional way
Delicious Library 2 - Keep a library of...pretty much anything that has a barcode. Movies / CDs / Power Tools / etc...
Disk Inventory X - Find out what's taking up all your HDD space.
Enjoy