Having used most of the distros mentioned so far, I thought I'd mention experiences in with the following:

Red Hat: Slow but stable, consumes more memory than I'd like but has top-notch hardware detection and lots of pretty GUIs for network configuring etc. A good choice for a newbie or someone looking to make the next step but doesn't want to jump in at the deep end.

SUSE: Worked ok for me, had some hardware problems and I don't like that blasted lizard appearing all over the place. Very similar to Red Hat in that it works well for newbies, is easy to install but still hogs memory a bit too much for my liking (although that might partially be down to KDE3).

Mandrake: In my experience, it either works great or goes belly up at installation. Very easy to use installer that can either guide you through or let you make choices if you're familiar with Windows and know how to partition your hard disk. Personally, I've had lots of problems using Mandrake on two machines, but the rest of the time it's worked fine.

Debian: Another one which is great when it works and sucks big time when it doesn't. Everyone boasts about how great the package management system is, but the releases are few and far between and you have to either do a dist-upgrade, use backports.org or install the software yourself to keep up to date. Debian didn't seem to like my network card at first (weird, because every other distro detected it and setup DHCP correctly) or my monitor/graphics card (had to edit XF86Config numerous times, which is not really a good thing). I would never recommend Debian by itself to a first-time user because of the difficulty of installing and also Debian users seem to be very defensive if you ask why something isn't working properly.

Slackware: The best distro I've found for making the jump from newbie to intermediate user. The text-based install scares people off sometimes, but it's really simple to follow and you can completely automate the package selection/installation process if you want (there are several modes from newbie to expert, to chose from, plus you can install everything without prompts if you want). The two disc 9.1 set that I have came with a good selection of Window Managers, including the latest versions of KDE and Gnome, and the only problems I've ever had were with my new LCD monitor - easily fixed by editing a couple of lines in XF86Config (yes, I know I criticised Debian for this, but with Slackware there were only one or two lines to change rather than half the file).

Gentoo: Ugh. I couldn't even get past the initial install stage - this has got to be the most unhelpful distro I have ever tried. If I wanted to try BSD, I'd install Free/Open/NetBSD. All the other distros guide you through step-by-step, whether this be through nice GUIs (SUSE probably wins hands-down in this area) or text-based prompts. I was also put off by the attitude of some people on the Gentoo forums, and the fact that the developers apparently file bugs with their kernel in the Red Hat bug tracker.

FreeBSD: Not really Linux but in a similar boat. Never managed to get X working properly but I would like to get a test box running just to see how it works with a GUI. Installation was similar to Slackware except for the problems of X.

Knoppix: Great for hardware detection prior to installing another distro or for showing off Linux to someone on their machine without installing it. You can even do a hard disk install, but whilst this worked for me, I didn't think it provided enough features.

In case you're wondering I'm a Slackware convert from Red Hat/Fedora (although I still use Red Hat on my laptop because it's what we use at uni and it's so much easier to standardise on one distro - but I may switch in the future). I miss up2date, but Fedora has the excellent yum for anyone who wants to keep their system up to date.