Acho que você está enfrentando 2-3 problemas aqui:
Definição de tempo de atividade
Três noves incluindo janelas de manutenção anunciadas ou excluindo? Com que antecedência você anunciará as janelas de manutenção?
Tempo de atividade do hardware
Isso só será dimensionado com redundância. Você nunca sabe quando vai quebrar e três noves significa apenas cerca de 9h tempo de inatividade por ano. Assim, mesmo um contrato de 4 horas lhe concederá apenas um tempo de inatividade (2 se for realmente corrigido dentro de 4 horas - mas isso não é exatamente barato para se obter). IMHO você tem que ter 2 servidores para isso
Uptime de Software / Serviço
Você vai definir o tempo de atividade por acessibilidade de ping, respostas HTTP, como? - Você pode facilmente resolver isso definindo com antecedência o que você considera "up" (ou se é mais fácil o que você considera "down" - mas isso seria enumeração de maldade)
No que diz respeito ao barato, não sei se por preços baratos você quer dizer custos iniciais ou despesas correntes. Você pode obter algum servidor barato em quase todos os lugares, mas provavelmente precisará de mais deles para descartar quebra de hardware ou adquirir um hardware decente com HP, Dell, IBM com custo inicial mais alto, mas uma probabilidade muito menor de quebra de hardware e assim terá um menor custo de funcionamento. Basta calcular o tempo de vida de uma pessoa que será mais barata.
Se você quiser apenas algumas URLs:
server4you foi muito legal para mim
EC2 com localizações georedundantes (UE e EUA) também poderia ser muito interessante
EDIT: Para ser claro quando digo 2 Machines quero dizer Machines redundantes por caso de uso (DB redundante, Web redundante, DNS redundante, redundante $whatever