I know as soon as I say this someone will holler at me, but I basically started with Slackware, and think it's a great distro to learn on. It's
worked well for me out of the box, and
requires you to do a LOT of editing of .conf files to get everything set up like you'll want, so you get
forced to actually
learn something as you go. It's only a good choice for someone who is committed to rolling up his sleeves and trying to learn though, to anyone else it will be frustrating, and

will be your new best friend very quickly!
just $0.02 from linux newb. (the user title is to identify the avatar, not represent my skillz)