How much do you want to get your hands dirty is the real question? Ubuntu will keep your hands fairly clean, though I believe it is based on GNome as its main GUI which in my opinion is no where near the best choice. KDE is a much better GUI all around.
Kubuntu is the version of Unbuntu that you probably want since it is based on KDE. You can achieve the same thing though by loading Ubuntu and adding KDE later, but Kubuntu has it all built in.
Mandrake - I used to use this ages ago, and it is easy, but I think it has seen its day.
Slackware is the middle ground. Its more a hackers OS though and it will get you familiar with command line commands more than the two above.
SUN10 - never used it and I don't know much about it personally. Probably pure Unix. Have fun with that.
Fedora - Basically free Red Hat. It is popular from a server perspective. Not sure you want to run it as a desktop OS however. You can freely use RPM pacakages with it though which makes it brainless to add new software to it.
Now if you really want to get your hands dirty and understand the core of Linux (Or the hidden things that any OS has in it), and you want you system to run faster than any other Linux OS or if you want your system to be as bloat free and customly tailored as possible, Gentoo is your answer. Gentoo is the only Linux OS I run at home. I have 2 systems running it and it is so customized, I compiled all code from the ground up (otherwise known as a stage 1 install or developers install). It is so customized, the OS as configured will not run on any other system than the one it is installed on. This leaves me with minimal hard drive use, minimal kernel size, minimal bloat, and I have compiled all of the speed options built into my hardware and use it all.
An example - I have it running on an X2 4400+ AMD, so I compiled in SSE, SSE2, SSE3, AMD3DNow, MMX, 64 bit, Multithreaded, ....... You get the idea. TO compare to Microsoft - they compile against i386.
Get the idea? Problem is, Gentoo will frustrate the hell out of you before you get it optimally tweaked, and it will take tremendous time since you compile all your own code. You could get a base system installed pretty quickly though, but forget getting a GUI installed quickly.
Since this is your first go around, I'd say go with Kubuntu. Just my 2 cents.
-S
__________________
 
|