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

Here's some more:

Programming in Linux

C++ IDEs:
Code::Blocks
Anjuta
KDevelop
Code Warrior
Eclipse
MinGW Developer Studio

Python IDEs:
Idle

.NET IDEs:
Mono Develop

Text Editors:
emacs
nano
vi
pico
NEdit
KWrite
Kate
GEdit
SciTE

Compilers:
Not really much to say here; Linux comes with all the compilers you'll ever need.

Gaming in Linux:

First-person Shooters:
Alien Arena
Cube
Nexiuz
America's Army (this is a really good one)
Tremulous

Strategy Games:
The Battle for Wesnoth (My favorite Linux game)
TA Spring
FreeCiv
Boson
Globulation

RPGS:
Neverwinter Nights (commerical game)
Adonthell

thank you both
nice job.

Please, use this thread to recommend your favorite Linux software (I should have mentioned that in the first post). Also include a link to an install guide if the software is difficult to install.