Start with Ubuntu. New version's out this week. If you like it, use that; if not, try Kubuntu. If you don't like either one, you're left with a few options, which basically boil down to:
1. do some serious research and tinkering to get stuff working exactly the way you want (whether it be another distro, another WM, or just a million little customizations);
2. wait 6 months for the next Ubuntu release and repeat.
I'm a Kubuntu guy (but have been meaning to give the default GNOME version another shot), so I'm around if you have any questions.
I've also been through Slackware and Gentoo, which are good places to start if you want to be FUCKING HARDCORE and learn everything from the ground up. Those are for somebody who wants to invest literally hundreds of hours but learn a lot doing it. Me, I'm glad I did it that way (because now I know my way around enough to fix shit if it breaks), but see no reason ever to do it again (knowing how to do something doesn't mean you want to do it if you can avoid it -- as I've said elsewhere, I never want to edit Xorg.conf again as long as I fucking live).