My experience with different distributions, or try MEPIS, you'll thank me
I've tried Debian. I got it working well on desktop with somewhat standard hardware, but on my laptop it was a nightmare. After the install, I couldn't get X to start. After hours reading countless man pages, checking online forums et cetera, I gave up.
I've used Mandrake (now named Mandriva after merging with Connectiva). The install was fairly easy. It used ReiserFS by default, a good choice (though I prefer ext3 because there are more tools). One of the complaints I have though, is that the install took hours. Literally. I've never seen a slower installer, why I can't say. But when you jump those hoops, it had good auto hardware detection, and was very usable. Because it is Red Hat (or FC take your pick) based, installing RPM's is easy. It has a package manager that knows what is on each install CD. To get software not included on the disks, you must compile from source or pay for it.
I've used Knoppix. I know everyone has used the liveCD, but I've installed it to hard drive. One of the many hidden secrets about knoppix is that from the terminal (running as su) you can run knx-hdinstall command and the installer is pretty nice and much quicker than Mandrake (though not as pretty). It is also Debian based, so apt-get, aptitude all work. Knoppix is a highly usable system.
I've used other live CD's. One of my favorites to have is Auditor. It is a rather complete system with great hardware detection (including wireless cards). It is primarily for security testing, and we've had great fun with it at college with all the wireless networks around. Maybe the newest version of Auditor fixed this, but the HD install always locked up for me.
Another great live CD is Helix. Helix will boot off a machine with no hard drive. Helix leaves literally no footprint behind. That is impressive. Basically it is for intrusion detection. If you've had a computer hacked, Helix is great for finding how and what the person left behind. That said, neither Helix or Auditor are for desktop use, but are specialty distributions.
I've tried Gentoo and Fedora Core 3. Like Debian, Gentoo was not so good at auto-detection of hardware. Fedora Core likewise. It seems that Gentoo, FC, Debian, Slackware (which I've never tried), form the 'harder' distributions others are based off of.
I used Ubuntu. It was very easy as everyone screams about. But I don't like Gnome much, and there wasn't much variety in available software. I moved to Kubuntu for KDE and it was just as usable as Ubuntu. Ubuntu is easy.
As a criticism, not of Ubuntu specifically but most "easy" distributions, getting additional software is more difficult than say Debian (my wife can use synaptic without thinking twice). So if you want a program not included, you had better learn ./configure ./install commands. This isn't bad, these commands are useful anywhere. For the average user Ubuntu (and about every other distribution) comes with everything you need really.
I tried SuSE and it was really a breath of fresh air. It detected everything on my laptop, the installer (YaST) was terrific, everything just worked. I am excited for the advent of OpenSuSE. I switched away because I didn't want to install everything else from source (some programs have binary distributions, such as Sun's Java) At one time I would have switched to OpenSuSE in a second. But for now, I've found my distribution.
MEPIS is perfect. The install CD works as a liveCD. Try it; if you like it, the installer is built in (no additional CD). The installer is very fast, very easy and has great auto detection. Because it is Debian based, programs like Synaptic, or Aptitude work flawlessly, making programs very easy to add. If your system gets messed up, MEPIS has tools (on the LiveCD especially) to fix Master Boot Records, et cetera. It is one of three distributions that auto-detected my non-standard wireless card (they are SuSE, MEPIS, and Auditor).
I've not had any problems with MEPIS. Because it is Debian based (and they test software extensively before adding it to an apt-get archive) some software released are slow in arriving, but it is near perfect. I strongly suggest MEPIS to anyone wanting to learn more about Linux, or just escape the M$ stranglehold.