Here's (in my opinion) some of the best Linux software available:
Stuff for your GUI:
Still using Gnome? Need a more powerful environment? Maybe you should try KDE. It's a matter of personal choice, but I prefer it to Gnome.
Allows you to download skins and anything else you can think of for KDE: wallpapers, window decorations, icons, clipart, etc..
The Gnome equivalent of kde-look.
XGL provides a 3D desktop appearance for your window manager. No, it isn't really useful, but it's totally awesome eye candy.
Firefox is a breath-taking web browser that blocks pop-ups, adware, and so much more! It's a must-have for any Linux user.
Opera is another cool browser, and it's debatable which is better: Firefox or Opera. It's up to you to decide. They're both awesome browsers.
Decent open-source media player.
VLC plays ANYTHING. If the format exists, you can be almost certain it will play. Always keep this on hand.
A jukebox style music player.
When you want to play games on Linux, you can either use the open-source ones (which usually suck), or you can try playing the Windows games:
Wine - http://www.winehq.com
Cedega - http://www.transgaming.com/index.php - Which costs money unless you cvs and compile it: http://transgaming.org/cvs/
And of course, once you're done having fun with Linux and need to get some work done, get Open Office:
Or for just a good word processor, try AbiWord: http://www.abisource.com/
Many of these programs may require you to compile their stuff. For you Linux newbies, here's a good compile guide:
Except for Debian, these are all relatively complex distros, and not good for the faint of heart. Try them at your own risk.
Add anything you feel I left out. ;)
Hope this helps