Additional information about various Linux distros is at http://lwn.net/Distributions
I started out with Red Hat Linux and loved it but unfortunately Red Hat discontinued their free Red Hat Linux product and concentrated on their Red Hat Enterprise Linux line instead. Fortunately, they started the Fedora Core project which is a community supported product that is free and is more or less the descendent of Red Hat 9. Both Red Hat linux and Fedora Core are very popular. Several people in the local Linux Users Group in my town us it. It comes preinstalled with quite a bit of software and is usually fairly easy for a beginner to configure. When I installed it on my computer it ran somewhat slowly and I never bothered to try to figure out why. I ended up using Slackware instead.
I use Slackware which is a hardcore distro that is less oriented towards beginners. It is a lean mean fighting machine distro. It does less hand holding for beginners in the installation and configuration process. It does not come with as much software pre-installed. Slackware is not an RPM based distro and has its own packaging system for programs. It also one of the few distros that use more of a BSD style initialization instead of the more common System V style initialization. One thing to be careful of is that when Slackware is first installed the iptables firewall is not turned on by default. On my computer Slackware seems to be fast and stable. In my opinion some of the other distros seem slightly bloated by comparison.
SuSE linux is a poplular well known distro that was recently bought out by Novell. SuSE can be downloaded for free or purchased in a box with manuals (and possibly some technical support too although I am not sure about that). It is an easy to install and configure disto that several members of the local Linux Users Group in my town use. I have not used SuSE myself and do not know much about it. It is an RPM based distro. The combination of SuSE Linux and the networking company Novell sounds interesting.
I have tried Mandrake only once briefly. It seems to be desktop oriented and tries to be user friendly. I believe it was originally a Red Hat derived distro and uses RPMs. Of course it could also be used as a server instead of for desktop use.
Vector Linux is a Slackware derived distro that is partially oriented to users that have slightly older computers. Vector Linux has lower hardware requirements then most other distros. It is much like Slackware although it tries to be slightly easier to configure. It is not as well known as some of the other distros. It seems to be lean, fast stable and not bloated. Here is a review of Vector Linux: http://madpenguin.org/cms/?m=show&id=2784
Debian is a popular distro that has a loyal following. I have never used it but from what I have heard it is a hardcore distro that is less beginner oriented. It uses its own packaging system instead of RPMs.
Knoppix is a Debian derived distro that boots and runs entirely from a CD without having to be installed on the hard disk. Linux users like to hand out Knoppix disks as an easy way to try out Linux. It can also be used for emergency recovery purposes when some other version of Linux will not boot up from the hard disk.
I have only used Xandros once. It seems to be a desktop oriented distro that tries to be user friendly. If I am not mistaken, I believe that Novell bought them out. Here is a review of Xandros at http://madpenguin.org/cms/html/47/3145.html
Linux From Scratch (LFS) is for users who want instructions on how to create their own working Linux system from scratch. I have not yet tried that.
Lindspire (previously known as Lindows) is a version of Linux that from what I have heard, tries to be user friendly and is marketed as an alternative to Windows. Wallmart sells a computer that comes with Lindspire pre-installed on it.
MEPIS is a Debian derived disto that one reviewer described favorably. I have never tried MEPIS myself.
I have never used Lycoris but here is a review that describes it as easy to install:
Turbo Linux is popular in Asia There is a review of Turbo Linux at http://madpenguin.org/cms/?m=show&id=1923