A mí me ha recomendado Suse, Kubuntu, Fedora, Ubuntu, Mandriva y Debian.
Curiosamente mi primera distro fue Mandrake/Mandriva, luego tuve Fedora, y ahora soy usuario de Debian. Además en cierto momento barajé la posibilidad de probar Suse y/o Ubuntu.
Eso sí, no ha acertado que adoro Knoppix (como LiveCD), y que en cierto momento estuve a punto de probar Gentoo; al final me rajé.