GuruZim says Debian, but his avatar says Slack...
Either one is a good choice. Debian is easily the best maintained tree around when it comes to Linux distros. I prefer Slack's more BSD-ish feel, myself.
I tend to avoid RedHat, et al. True, they make some things, such as installation, easier, but in many ways I believe they can make it more difficult to learn how the system actually works; this, to me, is more than half the point.
Depends on what you want. If you want something that will hold your hand and insulate you from technical details, then go for Mandrake I guess. I've never used it, but it's got a newbie-friendly reputation.
If, on the other hand, you want a cruel mistress who will force you to learn things on your own through a trial by fire, emerging as the master of your Linux domain, then go for Slackware. That's what I did (am doing). It's been an arduous journey but worth every moment.
If only The-W had the membership it once had. Ze Frank did this thing once where he helped a guy hitch rides across the country from one member to another. Of course it wasn't possible for the guy to be stolen, so that made things a little easier.