Gentoo is a great choice, but keep in mind, again, that you do spend a lot of time compiling.
But, if you choice is to actually learn how Linux works, theres only one distro that beats it. And it's nto really a distro. LFS really teaches you pretty much everything about Linux. Other than that, gentoo is great, Slackware is great, and Arch is great.
The more Newbieish distros like Mandriva and Ubuntu tend to try to hide the "under-the-hood" good stuff with gui tools. In all hoesty, I now feel much more comfortable with a CLI and a keyboard. The mouse and GUI can get in the way sometime. But, It might take time to get to that point, which is fine. It's really a matter of what you are looking for. Learn Linux, or just use the computer?