iTunes - Back in the days when I used Windows there was Winamp. After some time I switched to Red Hat and I discovered mplayer. Nowadays, I still use mplayer a lot, but all of my musics are organized and played from within iTunes, which is a great tool for this effect (not perfect, but very good indeed).
Desktop Manager - People have told me, when I switched to a Mac, that I would never have to use multiple desktops again, since I'd now be able to see all my windows at the same time, just a little bit minimized so they'd all fit the screen... those people have clearly never used a dozen or two terminals, browser, music player, mail viewer, talker and others at the same time. Desktop Manager is a *must*, for me. YMMV.
QuickSilver - I don't think I make as much use of it as possible, but it's a great utility. Just type Control+Space and start typing the name of the application you want to start. Wonderful for launching applications you don't really want to have on the desktop or in the dock.
Sidetrack - This little one allows me to use my touchpad in the same way (actually, in an even better way) I used it in my Compaq.
Firefox - Need I say more? Some people keep telling me how great Safari is... Nope, Firefox for me, please. The power of its extensions is too good to be thrown away.
Adium - The first messaging program I used in this iBook was Proteus. It has some serious flaws... Now I'm using Adium, and so far... so good.
and regarding mail... well, even though Mail has the advantage of integrating with the rest of the system, its power is still faaaaaaaaaaaaaar behind the one of Mutt
There are more, but I'll leave them for another entry