Agreed. I'd personally recommend either Ubuntu or Mint, they're the best beginner distributions at the minute. If you're thinking of using Ubuntu, wait 35 days or so and the new version will be out (saves you the hassle of upgrading). Mint should be fine to just get going!
I wouldn't recommend Fedora, it's suited more to a geekier audience and isn't tested that well (Fedora 15's liveCD had a broken installer for crying out loud).
Don't bother with Gentoo, it's interesting but seems rather pointless. (So much compiling). Arch on the other hand is awesome and once you've played with Ubuntu, I recommend giving it a go. Even if just in a
Virtual Machine. The wiki is fantastic, check the
beginners guide. Installing Arch is rather easy, but on the way through it you'll learn the basic ins and outs of GNU/Linux (Commands, CLI interface etc.) and how everything works together to make the complete system.
Hope that helps. If you need any more advice feel free to ask.