Mandriva is probably one of the most idot-proof distributions out there, and comes on 4 CDs (At least the last version I downloaded did lol), and this means that it can automatically install most of the required stuff. Add to this the EasyURPMI website for the updates/ legally restricted stuff, & this has gotta be one of the best all-round beginner distros.
If you want Gnome, the Ubuntu is by far and away the best out there, especially as it's usually the first to have new versions. However, this means that the KDE support is nowhere near as good. It also comes with far less stuff availabe by default, which may or may not be a good thing. (Mandriva lets you choose categories of common apps to install)
-Leezer-