Ponle Xubuntu 9.04, no tendrás problema. La versión 9.04 de Ubuntu ha mejorado el rendimiento con respecto a las versiones anteriores (8.04 y 8.10). Y poner una anterior a estas 2 no tiene mucho sentido.
No se que frecuencia de procesador tiene ese pentium III, pero con 512 de RAM vas sobrado.
Si quieres que vaya muy fluido, obviamente has de recurrir a una distribución Linux más ligera, pero añade complicación. Como nota que sepas que tienes crunchbang, que es Ubuntu pero con escritorio openbox.
Mejor que eso te recomiendo Debian o Arch. Debian es fácil instalarlo, pero tienes que configurarlo para que te vaya bien. Y Arch tiene una instalación complicada si eres novato y no tienes un mínimo de conocimientos. Eso si, con Arch te montas el sistema a medida y ganas rendimiento.