Xubuntu já dá bem para começar. Andamos instalando ele em Lentiums III e II da Vida aqui nos Install Fest. A instalação demora pra Burro! Mas depois de instalado ele desempenha bem. Agora, se for forçar a máquina, abrindo um monte de coisas ao mesmo tempo, vai ficar lento mesmo com essa quantidade de RAM. O problema é a quantidade de RAM e nem tanto o processador.
O Debian com XFCE consome apenas 46MB depois do Boot e não é tão complicado como o FluxBox ou o Slackware para um iniciante. Mas é bucha mesmo assim para quem nunca viu Linux.