Mori,
Se as suas máquinas são tão fracas assim talvez o melhor não seja usar o Ubuntu. É claro que nosso papel aqui, dentre outros, é promover o uso do Ubuntu, mas há limites para tanto. É preciso considerar antes o interesse dos seus clientes!
Eu também trabalho no serviço público e sei que muitas vezes a maior parte das máquinas são bastante antigas. Mas, em compensação, do que precisam a maior parte destas estações de trabalho: basicamente, uma boa suíte de escritório, algum bom navegador para fazer pesquisas, impressão fácil (o que, muitas vezes, significa suporte para máquinas bem antigas) e, talvez, em casos específicos, algum aplicativo multimídia. Instalar aplicativos é coisa que se deve restringir ao administrador do sistema, se possível, apenas o profissional do setor de informática. Logo, nem é mesmo necessário que se trate de um procedimento tão amigável, já que caberá exclusivamente ao funcionário.
Pensando nestes termos, acho que você poderia pensar em duas alternativas:
1) Instale o Ubuntu nos servidores e estações de trabalho, mas reduzindo bastante estas últimas. Nada de KDE ou Gnome: use o Xfce, que é muito mais leve e bastante fácil de usar (o que é difícil no Xfce não é coisa para o usuário, mas para o administrador). E instale apenas o que será estritamente necessário para cada setor.
2) Se mesmo assim, o sistema não rodar muito bem opte pelo Vector Linux. O Vector é desenvolvido especialmente para rodar em máquinas antigas, costuma "ressuscitar" verdadeiras velharias, é seguro, estável e relativamenta fácil de usar - em certos aspectos mais fácil até que o nosso Ubuntu (conta com um centro de controle, o Vasm, que é muito intuitivo e eficaz). E a versão standard do Vector conta com gerenciadores leves - mas muito bem customizados - que podem servir à perfeição para as estações de trabalho aí da Adm. Municipal. Não há suporte a Português Brasileiro nos utilitários administrativos, mas isto não constituirá nenhum problema para vocês, os técnicos. Tradução para o Português nos ambientes gráficos e aplicativos existe, pois a Vector é uma derivada do Slackware, que conta com bom suporte ao nosso idioma e uma comunidade bastante ativa no Brasil.
Evidente, que eu preferiria que você usasse o Ubuntu, mas se o resultado não for satisfatório, não desista do software livre. Se o seu problema é fazer funcionar um acervo de máquinas heterogêneo e um tanto ultrapassado é exatamente o Linux que lhe oferecerá uma solução.