For learning, Fedora and Mandrake (both mentioned above) should be excellent. I'm learning on Mandrake, myself and am rather enjoying it. I've heard many good things about SuSE as well, but the install didn't like my NIC, so I opted for Mandrake.
The Mandrake install was about as painless as possible (with the exception of the one lockup while trying to format my harddrive). Didn't take nearly as long as a Windows install either. I suspect that for those of us learning any of these would be about equal. One thing, if given the option, pick Gnome over KDE.
Oh, and stay far, far away from Gentoo for now.