First off, I recommend a virtual machine for testing systems. VirtualBox is good and free. You don't have to worry about anything and you can test as many systems as you want all at once till you find one you like. Without touching your partition table & file systems.
Ah Gentoo... Go with something else till you get your feet wet. I too used Gentoo but most of the time it's nice to use your computer to do stuff instead of doing stuff to your computer to use it, you know? Anyway there was some good advice not to use your main box for your first Gentoo install... heed it.
Ubuntu is popular, but so are Fedora, openSUSE, Mint, ... a hundred others.
I like Ubuntu myself as Debian is a very solid starting point (OpenSSH blunders aside). Just try every distro you think looks good until you find one you really like. Switching from distro to distro is pretty easy at the beginning. Once you know your way around a distro you might find things are different on another, but on the surface they're mostly similar.
I started dual-booting Linux about 6 years ago, made the total switch about 4 years ago. Since then I've also used Mac OS X, the BSDs, OpenGenera (look this one up!), and almost anything else I could get my hands on. Since then Linux distros have improved beyond my imagination, and when I use Windows these days I wonder how people live with such a barebones system (sometimes). I'm not a Windows hater, I have my beef, but a lot of the time it's the right tool for the job. It's not my first choice but it's not my last either.
I've actually found that on a really slow PC, Gentoo can be the ideal OS. It's incredibly lean and fast, and you can optimize for size, which is great for low ram systems.
If you have a box that old and it can't even run Xfce well ... use fluxbox! Seriously though put OpenBSD on it and use it as a router or something or recycle it out of its misery. You're putting too much effort into it by compling on the slow box or cross-compiling .... unless you're just having fun I guess.