Personalmente, si vienes de windows meteria una mandriva, mas que nada por que el cambio sera menos traumatico, queiro decir que los asistentes de mandrake son muy faciles, y en ubuntu tienes que tirar mas de linea de comandos, si bienes de windows puede ser un poco incomodo
Si ya antes tenias linux, ubuntu, siempre le le puedes instalar kde o kubuntu, si quieres rendimiento por encima de todo, entonces gentoo
Espero haberte ayudado
Un saludo
Edit: Mandrake o mandriva, es la costumbre xD