Pues puedes empezar con algun Live CD como te dijo linuxfilo knoppix live este esta basado en Debian por si una vez que lo conozcan puedes pasar a este, o empezar con Mandrake o Suse son muy faciles de entender.
Yo empece com Lycoris,Mandrake y Termine con Debian Sarge
Y he probado tambien Suse y Red hat (ahora Fedora)
Saludos
