Spotify
For listening to music off the internet. This definitely has become one of the pieces of software I would first install (on a Mac or any other computer).
Note: Spotify is currently available only in some European countries: Sweden, Norway, Finland, United Kingdom, France, Spain and the Netherlands. Wikipedia article has details.