I may be opening myself up to the firing squad here becuase you know some people are quite passionate about their favorite tools/distro etc. This isn't meant to be a 'best of' list but an example of how you can set up a solid desktop machine that will meet your eye candy needs but also have enough tools under the hood for the web savvy seeker.

Hopefully the list will also be of some help for non-GNU/Linux users who might like to take the plunge. Hence some of you already know many of this software comes standard with almost any distro, but I list them to give an idea of what you can get in a completely free 100% non MS computer.

Kudos for good suggestions:
f+; erom - ngrep was a good tool I didn't know.; Asura - good list of tools at http://www.insecure.org/tools.html; Zeppo Mexicano; agras; y and ;)

Feel free to add more, make corrections or suggest alternatives.

Distro

I don't wanna start a flame war or rehash discussions that are already all over the net but...

Ubuntu/ Kubuntu/ Xubuntu - Good choice if you're moving from Windows or just starting out. Ubuntu if you prefer the Gnome desktop, Kubuntu if you want KDE or Xubuntu for XFCE.

Gentoo - Good if you are into tweaking everything and you have a lot of time on your hands. Good for advanced learning and those who like to roll up their sleeves.

Somewhere inbetween those you can pick a raft of others. I like Fedora simply because I cut my teeth on RedHat. It's not terribly important. Try a few!

Desktop Environment

Yes, unlike windows you actually get a choice here. Choose your weapon...

Gnome - Pretty slick icons, look and feel. Is a true GNU desktop and uses GTK+ for development.

KDE - Maybe not quite as slick but has a ton of software, is older and highly customisable. Uses Qt for development framework which was controversial for not being completely open source.

XFCE - Very light-weight but also capable. Runs great on an old Pentium Pro 200Mhz machine or an xbox!

Common Apps for the Desktop

Just because you have an Open Source operating system doesn't mean you have to look at a vt100 session all day. The days of GNU/Linux being considered a 'poor mans windows' are long over. Of course you can always go to a shell (command line) if things get rough.

File Manager
Krusader - Highly customisable and puts windows exploder to shame.

Audio Player
amaroK - Great audio player and media library with amazing features such as auto album cover and lyrics download. If you don't need quite so many bells and whistles a more lightweight option would be xmms which is styled after the popular WinAmp player and supports skins, input plugins etc.

Video Player
MPlayer - For dumping/viewing any streaming content.

Emulator
wine - If you can't bear to part with some of your precious windoze apps never fear, you may be able to take them with you. My beloved Edit Plus runs like a dream under Wine.

BitTorrent Client
azureus - It's Java, so it runs fine. You need torrents for all those distros you wanna try.

Instant Messaging
Gaim - Supports just about any flavour of messaging you can imagine.

News/RSS Ticker
KnewsTicker - Comes built into KDE and scrolls everything you want to know across your desktop.

Terminal Services Client
rdesktop - Sometimes you need to use remote desktop to get into windoze from afar. Yes, you can access your XP box directly from your GNU/Linux desktop but you may be interested in this hack which allows multiple users to logon to a XP machine at the same time.

Full Featured Office Suite
Open Office - Spreadsheet, word processing, presentations etc.

PDF Reader
Adobe Reader - Not Open Source but a free download and pretty slick imho. If you really need an Open Source alternative try KGhostview.

Diagrams
Dia Diagrams - All sorts of structured diagrams such as network topologies, UML, electrical circuits, schematics etc. If you are into UML you might also like to try Umbrello.

Graphics
The Gimp - Photo manipulation, retouching etc. Feature rich with everything you would expect from a top graphics app.

Quick Image Viewer
kuickshow - Because you don't want to open a full blown graphics app everytime you browse through your photo collection. Kuickshow is simple, fast and discreet. Supports slideshows and all the usual fare for an image viewer.

Ripping CD's
Kaudiocreator - Frontend for ripping and encoding audio files. Supports CDDB lookups, batch job scheduling etc.

Web Browser
Firefox - No need to explain much here. Ok, ok, you can have your beloved Opera too.

Disk Space Monitor
kwikdisk - Uses KDiskFree to monitor disk capacity at a glance from your system tray.

CPU/Memory monitor
KsysGuard - Helps you see what's going on. Customisable and can be left running in your taskbar.

IRC Client
XChat - Cross platform IRC client.

FTP Client
gFTP - Supports FTP, FTPS, SSH etc, including FXP transfers.

Networking Tools

Anonymous Web Browsing
Tor & Privoxy - So you don't leave a trail behind you.

Network Analyser
Ethereal - When you want to see what's really going over the wire. Snort is also popular for analysis and intrusion detection.

Wireless Sniffing
AirSnort & WEPCrack - Because sometimes you need to know what your neighbours are up to. Also check Kismet.

VPN & IPsec
Openswan - Openswan is a fork from the now discontinued FreeS/WAN project.

Firewall
Netfilter - IPtables is popular for firewalling, NAT masquerading and packet mangling as it is built in to most kernels. Also see SmoothWall for full blown standalone firewalls.

Games

Ok, so Linux isn't exactly the platform of choice for gaming but these free offerings show that the barrel isn't empty and there are some gems around.

Platform
SuperTux - Sure this concept has been used before? Maybe ask your kids...

Space Shoot'em up
Project Starfighter - Top quality game originally developed for Amiga but ported over to Linux. Also check out Chromium for a great looking/sounding mindless shooting game.

OldSkool
Freedroid - C64 fans who worshiped Andrew Braybrook may travel back in time to 1986 with this addictive puzzle/shootemup.

Into the Emulator Scene?
XMame - All the usual MAME fare right from your desktop. Amiga fans can't go past UAE. Anyone remember the first time they saw Red Sector Megademo?

Server Stuff

Never under-estimate running your own server for a better understanding of how other people's servers work.

Web Server
Apache - One of the best known web servers on the net. And completely free for you.

Web Scripting
PHP - Powerful html embedded language used for dynamic web pages.

Database
MySQL - Popular free database that integrates well with Apache and PHP. Some prefer PostgreSQL as they claim it supports more advanced features. Also there are concerns about MySQL's future now that Oracle have bought the underlying engine which is supplied by Innobase.

Web Stats Reporting
Webalizer - Very common as it comes with a few distros.

Web Proxy Cache Server
Squid - You wouldn't want to accidently leave this running somewhere. Say at an internet cafe for example.

More Tools from the command line

Some essentials for your toolkit. Most come included in standard distros.

Text Matching
GNU Grep - It's power may not be immediately apparent. Use the pipe (|) to unleash it.

Mirroring or dumping down whole sites
WgetPro - It's the same GNU Wget but with extra features such as downloading from streaming URL's.

Detailed System Info
top - System summary and task info in one command.

Privacy and Encryption
GPG - Public key encryption software. Because you don't always want to send everything in plain text.

Software Updating
yum - Download, install & upgrade software automatically. It's true!

Network Connection Testing
GNU netcat - for testing IP network connections. Check out the essays right here on the amazing netcat.

Network Scanning
nmap - Port scanning tool to easily see network connections.

Packet Matching
ngrep - The power of Grep for network packets.

Binary Tools
GNU Binutils - Strings is an example tool for quick viewing in binary data.

Good Scripting Language
perl, ruby or python.