I'm also new to Linux. My first distro was Fedora Core3, and these guys here will tell you, I got plenty frustrated with it. I was posting asking someone to please tell me how to get it off my machine, short of running over it with a truck:-). Since then, I re-installed win98, seldom if ever use it. I installed FC3 again, in another partition, and began to get more familiar with it, still a beginner! And then I installed SimplyMEPIS, that was a very easy install compared to FC3, but, I just couldn't get it to work well for me, and again, I am a newbie at this, so it was probably more my inability, than the OS (SimplyMEPIS).I just liked the way FC3 looked an acted more than mepis. And now since I took some advice from here, and did the custom install, and selected everything on the install, well, lets just say right now I don't see myself turning back. I like what I got now. So what it boils down to is personal preference.
 
Justbill

As Justbill says, it's a matter of personal preference. Remember though there are other DE's also besides just the big two. There's Blackbox, Fluxbox, Windowmaker, XFCE, and my personal favourite, IceWM, just to name a few. The big two are great if you want a lot of Windows like tools and utilities. If you need mean, fast and clean, consider one of the others..

I've also had Knoppix for a little while and liked the way I had my KDE desktop configured with superkaramba running a bunch of cool applications on my desktop, transparent menus and taskbar, and etc. with very low cpu resources, but now I've been using ProMepis and I have configured it also to make it look just like the way I had it with knoppix but a little more advanced though with cool desktop backgrounds and a 3Ddesktop manager.
Personally I like KDE more than Gnome and this is probably because I stopped messing around with Gnome, which I have heard so many good things about it as well. You can also configure Gnome to look as fancy as you want it to look as I have seen in some of the screenshots posted at http://www.gnome-look.org/. I have read stories where someone had configured their gnome desktop to look just as a MacOSX desktop and you wouldn't be able to tell the difference. I remember I used to mess with gnome when red hat 8 came out. So I guess both are excellent window managers and same goes for IceWM, but for now KDE seems to be the most popular.