Debian, Slackware, Arch, Crux и иже с ними заработают без особых проблем. Правда, иксы могут подтормаживать, так что ставь что-нить лёгкое. Fluxbox или что-нить подобное.
Да хоть последнюю. Главное, wm полегче и основательно напильником пройтись. Если есть лишняя неделька, то лучше последнюю генту поставить. Правда, глаза станут красными.
Генту рулит) пакеты по тяжелее конечно пол дня будешь собирать, но с другой стороны, какие тяжелые пакеты могут быть для такого компа... я на 600мГц пенёк за 3 дня поставил всё и заточил. вполне комфортно