Eu 'pessoalmente' recomendaria o Debian i386. É relativamente simples de configurar e tem um ótimo histórico. O Ubuntu é legal, mas não é ideal se você não sabe como ajustar alguns dos recursos que vêm pré-instalados. Mais uma vez, esta é apenas minha opinião pessoal.
Edit: Se você está disposto a gastar algum dinheiro, você pode querer verificar uma instância do Micro EC2 da Amazon (aws.amazon.com) ou um 512 Linode do linode.com. Eu usei tanto para o trabalho quanto para as duas opções baratas.