Gentoo isn't particularly hard, you just need to be able to READ (This is a dying skill...)
But, unless you have several days to spare, I wouldn't start off on Gentoo - Most Linux newbies end up re-installing their distro a few times to get it how they want because they aren't skilled enough to mod it once it's in place (Not a trivial thing if you don't know what you're doing lemme tell ya!!

), and Gentoo is painful to install (IMHO! And I'm a Slackware user!!

), espescially if you're new because you need to do a LOT of reading.
If you put the effort in 'tho, you get one of the fastest setups possible

What LiveCD were you using?
Most Distro's feel VERY different from one another, and if you're used to, say, Knoppix, you don't want to use something that has a Gnome desktop because it'll confuse the heck out of you.
If your LiveCD has a self-installer, then I'd go for that assuming it does the job for you to begin with.
Alternatively, a good newbie distro is Ubantu (Ubuntu?) - Debian based, so it has apt-get which is a really nice installer system. It's not as Kitchen-Sink as other distros, and seems quite clean to use.
Like Knoppix, you can do most of everything you need through GUI, although as with any distro I recommend you at least get comfortable with the CLI at some point if you intend to push the disto beyond it's initial install setup

I personally compile everything from source, but I hate portage so I use a hacked Slackware distro as a base and make my own tgz packages to stick things on top of it. Life's too short 'tho, so I might actually have to learn howto use Gentoo properly for my next run...
