Hola,
Como recomendacion a distribucion las que te han nombrado estan muy bien , yo quiero hacer mi pequeño aporte dejandote el siguiente enlace:
http://distrowatch.com/dwres.php?resource=popularityEs una página con un ranking de distribuciones mas buscadas, obviamente aparece una cantidad abrumadora y la inmensa mayoria no soy las mas indicadas para un usuario que se inicia en linux, o algunas son distribuciones especificas para servidores, etc.
Sin embargo me atrevo a decir que con las 7 primeras te las puedes arreglar siempre consultando alguna ayuda, wiki, etc.
Empezando desde la 1º Mint es muy amigable al igual que ubuntu, ambas estan basadas en debian.
Fedora esta basada en redhat al igual que CentOS y asi nos podemos pegar la noche.
Si ya has usado Mint y Ubuntu, fedora es un cambio interesante , si nunca has utilizado ninguna de estas distros para empezar podrias probar : Mint,Ubuntu y sus variantes ( se diferencian mayormente en el entorno que incorporan, gnome shell,unity,kde,lxde,xfce,etc.)y aunque no la he probado tengo entendio que Mageia es una distro muy indicada para principantes.
Espero que te haya servido de ayuda.
Un Saludo,
Heli.