Xandros Comes with KDE as the default I think.
as for the difference between KDE and Gnome, there are a few, but they are both highly customizable and you could probably make either one look however you want with a bit of work.
KDE is qt based, while gnome is gtk
KDE has a 'start menu' type of thing by default which you use to access basically everything, while Gnome typically has multiple menus by default (you can change this though)
Both have panels that are easy to modify and edit and you can add launchers and various odds and ends too (system monitors, for example)
for KDE screen shots:
and I couldn't find anything like that for Gnomes site so here's an image of Fedora running gnome: