Debian è molto valida e stabile.
Ha un gestore di pacchetti ottimo, e con pochi comandi da terminale puoi ritrovarti con un sistema completo ed efficiente.
E' da poco uscita la versione 4.0, reperibile
qui. (ho supposto che tu abbia un comune x86)
L'unico neo è l'installazione davvero minimale per quanto riguarda l'edizione CD, ma per quella dvd non saprei dirti.
Comunque al massimo puoi farti un giro
qui per vedere un po' le ultime distribuzioni.
(Il mio consiglio è sempre debian o una debian-based per la prima volta, come *ubuntu)