I'm familiar with Red Hat, Mandrake, and Gentoo. From my understanding Red Hat is stopping production of their free distro next year, and discontinuing features like up2date, so I wouldn't recommend it for that reason. I actually prefer to use Red Hat. In my opinion Mandrake is the best for new linux users. The nice thing about Gentoo is it uses the BSD ports collection, so updating software is easy and its pretty easy to use for a novice as well. My recommendation is Gentoo, but Mandrake is a close second.

Again this is just my opinion.