I'll say Kubuntu, just to be different ;)

I personally prefer KDE to Gnome, so I pick Kubuntu over Ubunutu, but otherwise they're the same. I started out on Linux with Gentoo, and at first I felt kind of l33t compiling all of my own packages from scratch (mozilla == long time), but I've moved past that stage and now use Kubuntu on every system I own. It's good for newbies, and it's good for power users (I'm a professional developer and I use Kubuntu at work).

To see if you like it, just boot it up with the CD in the drive and take a spin around - the install disk is also a LiveCD that runs entirely in RAM.