You could save a lot of time by trying different distributions via Live CD/DVD. (Many distros install discs actually double as an installer and a live CD.) Obviously you don't want to do this long-term but it would be an easy way to test drive and see which stock interface appeals to you before jumping in.
I'd definitely go with a major distro so that it's easy to find setup/troubleshooting instructions online. Different distros may store files in different locations so even though all Linux flavors are largely similar, it can be really frustrating trying to look for a certain config file and realizing it's not in the same place as the directions say it should be. Once you're more experienced you'll know where to look but it can be a deal breaker when you're just getting started.
Some to look at are Ubuntu, Mint, and Fedora. Personally I prefer Debian-based distros but that choice is probably not very relevant until you start diving deeper into things.