Uma solução Linux Terminal Server parece um bom ajuste. Você precisará de um PC razoavelmente poderoso como o servidor, como você mesmo sugeriu. Em seguida, conecte-o a vários PCs antigos e baratos e use-os como clientes do Terminal. Isso deve dar um bom desempenho (exceto para elementos gráficos pesados como aplicativos 3D e vídeo), e você pode reutilizar o hardware antigo.
Ver, por exemplo, o Projeto Linux Terminal Server para informações e HOWTOs.