A mí siempre me ha gustado también Gnome. Dicen que en la versión 2 ha subido bastante la velocidad sobretodo en Nautilus.
De KDE pues no te puedo decir mucho, pero siempre se ha comentado que para los novatos se parece un poco mas a windows.
Los 2 son muy buenos, es cuestión de probarlos y elegir el que más se adapte a nosotros.
Los temas, pues son como los antiguos temas de Windows, que sirven para cambiar los colores, el tipo de ventanas, etc...
Los gestores de escritorio son otra cosa, es el programa que se encarga de manejar el "dibujo" de las ventanas, como interactuan con el ratón, etc...Gnome y KDE ya vienen con el suyo propio, pero en gnome puedes cambiarlo y utilizar otros como Enlightenment. También puedes utilizarlos a secas sin utilizar ninguno gestor de escritorio (KDE, GNOME, XFCE): WindowMaker, Fvwm, TWM, AfterStep, BlackBox, etc...
Pero con un equipo potente me quedo con Gnome y nautilus.