Dificil elección. yo uso los dos cada uno en un pc diferente, kde tiene algunas aplicaciones que para mi son insustituibles: amarok, k3b y konkeror, gnome en cambio es mas simple y sencillo, igual puedes usar aplicaciones de kde en gnome y viceversa.Kde recuerda mas a windows.
Para empezar quizas ubuntu/kubuntu sea mas apropiada.
Por lo de i386-i586 no has de preocuparte (salvo que tengas un AMD64)
Saludos

Es como tú dices, cuestión de gustos, a mi personalmente me gusta más el KDE que es el que uso desde hace un par de años

Yo voto por Gnome, por su simplicidad, adaptabilidad y configurabilidad (esta ultima palabra no se si existe)
Aunque como bién dicen los demas compañeros, es cuestion de gustos, yo, por ejemplo soy un enamorado de Gnome y no soporto KDE, antes me quedaria con XFCE.
Sobre gustos, colores.

Opinion de novata:
Ya hice mis pinitos en linux con Mandrake cuando iba por la version 7 u 8... Pero hace como 4 o 5 meses me dio por borrar XP y probar de nuevo. Primero probe kubuntu. No me preocupe por configurar nada, o sea que lo use tal cual queda cuando lo instalas. No me gusto. No me aclaraba con las cosas...
Entonces probe ubuntu. Se me hacia mas manejablre, asi que me quede con ella. Me falta mucho por hacer, voy configurando conforme lo voy necesitando, pero no me preocupa, hay muchisima info por internet. La moda como han dicho por ahi arriba.

Es cuestio de probar...

Mandriva es una sabia elección. Los paquetes i586 quiere decir que necesita un Pentium mínimo. i386 está optimizado para un 80386 y un i586 para un Pentium. Además los kernel compilados por Mandriva trae de serie activadas nuevas funciones que permite una ejecución más rápida.

En cuanto a KDE o GNOME, yo prefiero KDE por su vistosidad y su gran configuración. Pero no te preocupes, la ONE permite probar una de las dos versiones y luego instalar de una manera muy sencilla. Una vez instalada se comporta como la versión en DVD y puedes instalar lo que quieras desde los repositorios que hay en Internet (más de 4000 paquetes) y no te olvides de los PLF.

Luego es cuestión de probar, probar y probar.