You'll love KDE. It has always been one of my favorites. Plus the close integration with Qt makes it even better.
I've used gnome a lot lately too though. A lot of people hated the new Gnome 3 changes, but I didn't mind them.
It's not as full featured or nice as KDE though. But sometimes KDE acts a little weird due to some of the opengl stuff.
And if all else fails, you can try arch. It isn't an easy to set up distribution but it's cutting edge. So everything is the newest of the new. Makes for a lot cooler of a linux experience in my opinion. :)
Setup is not for the faint of heart though. There's no GUI, and I usually use a linux boot disk to get it going (one from sysreccd).