Stay away from Gentoo if you're just learning the OS... It's meant for people who really want to get every ounce of power out of their systems and know how to go about doing it. It's a good distro to move to later once you are comfortable with Linux.
Now, are you looking to Linux just to replace Windows and want one that's easy and ready to go out-of-the-box? Or are you looking to learn the OS and want to become comfortable enough with it to be able to go in and tweak the hell out of it?
If you're looking for out-of-the-box ease, check out one of the Debian spin-offs listed above. (Though I'd normally recommend Fedora, doesn't get much more simple than that)
If you're looking to invest some time and learn Linux, I highly recommend Slackware. It's the distro a lot of people cut their teeth on when entering the Linux world. I found it was the perfect mix of user-friendlyness and hard-core techno geek. It will force you to read a lot of how-tos, you'll spend your first few days at the command prompt with no GUI most likely as you just get your bearings straight. This is the best way to learn Linux as once you get a GUI, you're less likely to go in with a terminal window and do things manually. GUIs are great, but they hurt learning.
My $0.02