If you're fairly new to Linux, I would stay around the 'easier' to use distros...such as Mandrake, Redhat, and SuSE. Things like pure Debian and Slackware are harder to use, but much more customizable and powerful. Redhat is based on Debian. I've always liked that one. The last time I tried Mandrake I couldn't get the thing to use my laptop's display...so I gave up on that one, and I haven't tried the latest version. I wasn't a great fan of SuSE...but there are many people who will tell you to go and download that one immediately.
Knoppix, also Debian-based, is amazing for what it does...and that is boot entirely off the CD in a couple of minutes. It flawlessly detects hardware by itself, and boots into a KDE environment without touching the hard drive. It's great for trying out Linux, though you may want to just go with something you intend to keep if your download speeds are that low. Not that you can't keep Knoppix...you can open the terminal and do an hd-install to keep it if you like it, and it's great...but keep in mind that it wasn't initially designed for that. I've used it once to do a backup of a computer so infested with spyware it took about 20 minutes to boot windows...there was no way I was going to get anything done in Windows, and the data was important (my father is a doctor...so what was on that computer could seriously not be lost) so I booted Knoppix and flawlessly accessed the FAT32 partitions, backed up the necessary data, and reformatted the drive. Knoppix saved the day. It's great to have a completely bootable CD like that...amazingly useful. Testing hardware, trying out Linux, testing a network, dealing with partitions, making backups of drive contents, and much more.
edit: I just noticed 'Gentoo' on the poll...I have a friend who's using Gentoo as his primary OS...it's supposedly great, but it's also apparently a very advanced Linux. Something probably not for people new to Linux (like myself