1st Time Linux

I'm going to try Linux out for the first time, installing it on a 700mhz Celeron computer. Which distribution is "best" for a first-time user? I've heard RedHat and Mandrake are the easiest, but am trying to get an over-all consensus.

Also, what's the difference between KDE and Gnome?
Thanks.