RedHat: Large user base, some support from companies
Mandrake: slow but good for the "not so bright"
Debian: fast, easy with apt (and related packages), lets you do some work, but behind the times.
Slackware: Fast, no packaging system, lets you do some setup work, also behind the bleeding edge.
Gentoo: Fast, takes a while to get it setup, lets you build packages instead of just using binary packages, you must have a lot of time on your hands.
The BSDs arent Linuxes but here they are:
FreeBSD: Fast, plenty of ports, installs on a whopping 2 whole platforms.
NetBSD: Installs on everything but toasters (thats in the works), mostly an educational project. Highly portable, fairly speedy, should let you do plenty of the fun stuff setting it up.
OpenBSD: Fast, small, portable (9? platforms). No SMP, exists in a world where bleeding edge is pretty damn stable (ie behind the times a bit). Focuses on security.