Here's (in my opinion) some of the best Linux software available:
Stuff for your GUI:
http://www.kde.org/
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.
http://www.kde-look.org/
Allows you to download skins and anything else you can think of for KDE: wallpapers, window decorations, icons, clipart, etc..
http://www.gnome-look.org/
The Gnome equivalent of kde-look.
http://www.novell.com/linux/xglrelease/
XGL provides a 3D desktop appearance for your window manager. No, it isn't really useful, but it's totally awesome eye candy.
Web browsers:
http://www.mozilla.com/firefox/
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.
http://www.opera.com/
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.
E-Mail clients:
http://www.mozilla.com/thunderbird/
http://kmail.kde.org/
Music players:
http://www.mplayerhq.hu
Decent open-source media player.
http://www.videolan.org/vlc/
VLC plays ANYTHING. If the format exists, you can be almost certain it will play. Always keep this on hand.
http://www.gnome.org/projects/rhythmbox/
A jukebox style music player.
Windows Games:
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/
Productivity:
And of course, once you're done having fun with Linux and need to get some work done, get Open Office:
http://www.openoffice.org/
Or for just a good word processor, try AbiWord: http://www.abisource.com/
Installation:
Many of these programs may require you to compile their stuff. For you Linux newbies, here's a good compile guide:
http://www.tuxfiles.org/linuxhelp/softinstall.html
Oh and just let me throw in my favorite distros while I'm at it :)
Gentoo
Slackware
Vector
Debian
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