Those distros are OK, but if you know NOTHING about Linux, get your feet wet with Mandrake or something more user friendly first. There's quite a few distros to start with now... Knoppix has a lot of good noise around it. Gentoo and Slackware are relatively hard core and hands on.
KDE and Gnome are the biggest players in the desktop scene. They draw your windows, manage your desktop, provide libraries for applications to run with. It's much more than just a desktop, but that's the bit you see. They are individually themable (like StyleXP there?), but they are like the Windows Desktop is to Windows. In fact, to illustrate that, you can try LiteStep for Windows, and swap out your desktop shell for something quite different.
As for eyecandy, they can add the usual stuff. Transparency, fades, backgrounds, window decorations, pretty icons. Audio effects are there too. Browse <A HREF="http://art.gnome.org/" target="_new">http://art.gnome.org/</A> and <A HREF="http://kde-look.org/" target="_new">http://kde-look.org/</A> to get some ideas.
Honestly I don't know about the "hard part". If you dive into Slack or Gentoo there might be some head scratching over some configuration and what not, but more mainstream distros are generally pretty painless.
<i>Knock Knock, Neo</i>