Here's a list of my favourite software that I've put together. I've gotten all this software to work perfectly. Feel free to add your favs to the list
Games
1)Super Mario War
Super mario war is a great game for 1-4 players. There are many maps and many different types of gameplay to choose from. Although playing alone is fun, I highly recommend playing with a friend... because the bots aren't exactly the brightest crayons in the box.
http://smw.72dpiarmy.com/

2)Frets On Fire
Frets On Fire is a great Guitar Hero clone that's played by holding your keyboard like a guitar, using F1-F5 as frets, and the enter key as a strum bar (of course, these controls are configurable). You can add your own songs and configure where you want to have to press which notes, or you can even import guitar hero songs.
http://fretsonfire.sourceforge.net/

3)Wormux
Wormux is an extremely fun game to play when you have friends over (2-4 players), or online. It's a clone of the game Worms. You get to battle your team of animals against others in a completely destructible environment. I'd say the only downside is that there's no way to play 1 player because of the lack of bots.
http://www.wormux.org/phpboost/news/news.php

Graphics
1)GIMP
Most of you have probably already heard of GIMP, but I'll go ahead and add a description anyway. GIMP is a great image editor/ paint tool. It has amazing capabilities, especially if you take the time to read a few tutorials.
http://www.gimp.org/

2)MeMaker
This is just a fun little program for making a display picture for your computer user (you can also just save them on your computer for other uses). You're given different heads, colours, eyes, noses, ears, mouthes, noses, etc... to choose from to form your own character.
http://memaker.org/

3)Ktoon
Ktoon is a frame-by-frame animation program. It's pretty fun to play around with, or to make short animations with, but I can't see it being used for a serious animation project. It can supposedly export to all sorts of formats, but mine only saves as .ktn.
http://ktoon.toonka.com/

3)Clash
Clash is a frame-by-frame animation program based on Pencil. It's pretty much the same program (it's in its early stages), but exporting animations actually works (unlike the original pencil animator). With Clash, you can export as .ogg, .swf, and more. I haven't gotten much of a chance to use it yet, but it looks pretty promising. I've seen some animations made with Pencil, and they're pretty good... plus it has a cool slogan.("Clash: Freedom in a flash")
http://geesas.sourceforge.net/clash/

4)Synfig Studio
I can't exactly say how great this animation program is, because i haven't learned enough about it. I've done some experimental work on it, and the results were pretty good. Synfig uses vector graphics, and it uses tweening rather than frame-by-frame. I've seen some things done by other people using this program and, i must say, they looked really great.
http://synfig.org/

Internet
1)aMSN
aMSN is an MSN clone. It works great and has almost all the same features as MSN (plus a few extras..). You can even add plugins for more functionality! Although this program works great, many will complain that, even with its many different themes, it's one ugly program. And it is. But you should learn not to judge programs by their exterior. It's how they work that counts.
http://www.amsn-project.net/

2)Chrome
Google Chrome BETA was released for linux not too long ago. Once it came out, I immediately ditched firefox just to try it out... and i have no intention of going back. Chrome is feature-full and very fast. One of my favourite things about it is that if one tab crashes, the whole browser doesn't go down with it. You have the option to either wait for the tab to recover, or close just that tab. There are way too many cool things about this browser to mention here, i suggest you try it out for yourself.
http://www.google.com/chrome

3)Frostwire
Although Limewire supports linux, that doesn't mean that frostwire should be tossed aside and be considered an alternative. Actually, it should be the other way around. Frostwire runs much better than limewire in the sense that it won't make your computer lag like crazy. The results are just as good, and you get max-speed downloads without having to pay for a pro version. If you're using limewire, i definitely think you should consider switching to frostwire.
http://www.frostwire.com/

Sound&Video
1)Miro
Miro is a podcast downloader/viewer. You can add channels, download videos/audio, etc etc. And it's really good at playing HD videos. You can add youtube channels, download torrents, and even play videos that are already saved on your computer. Although i can't currently use it due to the fact that i'm having issues with video performance, I used to have so much fun with it (and i made my internet provider happy to make money off of me for going way over my download limit).
http://www.getmiro.com/

2)LMMS
LMMS (linux multimedia studio) is a great music making program. With LMMS, it's fun and pretty easy to put together a nice sounding song whether it be techno or metal. Just choose your instruments/sounds, play around with some notes, and put it all together. LMMS is a program that you can figure out how to use just by playing around with it... although you can probably do a lot more with it if you read a few tutorials... (PS: it supports FruityLoops Studio file imports).
http://lmms.sourceforge.net/

3)MiniTube
MiniTube is a fun little video player that streams videos from youtube. "What's so fun about that?" you may ask. Well, the fun thing is that, rather than picking a video, watching it, and then picking another, MiniTube allows you to type in a keyword (or multiple keywords) and then it plays a bunch of videos related to your search. (you have the option to see the playlist, skip through videos, etc)
http://flavio.tordini.org/minitube

4)OpenShot
OpenShot is a pretty good video editor for linux. Once again, i haven't had much of a chance to use it, but it's the best i've found so far. It has a few effects, and it allows you to cut and do other basic editing things.
http://www.openshotvideo.com/

5)LiVES
LiVES is another video editor. Although i find that it's pretty ugly and gets a little annoying at times, It comes with a lot nice video effects.
http://lives.sourceforge.net/

6)Songbird
Songbird is a music-based internet browser. It's basically a music player that allows you to browse the internet while listening. It has a lot of nice features for your music such as fetching album covers for songs, fetching lyrics which you can save, it can even sync with your ipod. It also has a lot of nice add-ons to make it more feature-full.
http://www.getsongbird.com/

7)Audacity
Audacity is a good Audio editor with some really good features. It allows you to cut out sounds, copy/paste, generate static/tones/etc, add effects, and more. It also has plugins to add features. You can make some really good sounding things with it, it's pretty professional but easy to use.
http://audacity.sourceforge.net/

Other
1)Ailurus
Ailurus is a program that gives you tips on how to improve your system. It tells you which programs do what, and allows you to install them. It even allows you to apply settings without having to open a terminal.
http://ailurus.cn/

2)Wine
Everyone should have Wine.. just in case. Wine allows you to run windows programs in linux. Although it works for most programs, there are quite a few that aren't supported (you can find out which programs are supported by visiting their site.
http://www.winehq.org/