Primeira edição : Que tipo de hospedagem (compartilhada, virtual ou dedicada) atenderá aos seus requisitos?
A hospedagem compartilhada não funcionará, pois você precisa de acesso root. A hospedagem virtual (VPS) pode ser muito mais barata que a hospedagem dedicada, e não vejo nada em seus requisitos que exija hardware físico dedicado. Em junho de 2011, um VPS não gerenciado (leia-se: suporte técnico mínimo) de 512 MB, baseado em KVM, começa em torno de US $ 20 / mês, muito abaixo dos planos de hospedagem dedicados mais baratos. Na verdade, os provedores de hospedagem mais dedicados não se incomodariam em oferecer um servidor com apenas 512 MB de memória. (Os preços mudam ao longo do tempo, mas você pode encontrar ofertas atualizadas no WebHostingTalk [veja abaixo].)
Os provedores de VPS mais baratos geralmente usam o OpenVZ / Virtuozzo. Na minha experiência, o OpenVZ / Virtuozzo também facilita que provedores menos éticos vendam demais o hardware. Alguns provedores oferecem soluções KVM (Kernel Virtual Machine), que geralmente são mais caras porque é mais difícil se livrar da memória com provisionamento insuficiente.
Segunda edição : Como você pode escolher um bom provedor de hospedagem?
Não quero comentar sobre nenhum provedor de hospedagem virtual específico, mas avisá-lo de que há algumas empresas de hospedagem TERRIBLE no mercado hoje. VPS hospedagem é um negócio cutt-garganta, e as margens de lucro são muito finas, por isso há muita pressão sobre os provedores para cortar custos. É difícil dizer a diferença entre bons e maus provedores e, às vezes, uma boa empresa de hospedagem vai mal, devido a mudanças na administração ou na política. (Eu tive isso acontecer comigo, um par de vezes.)
A fim de eliminar os piores provedores de VPS, eu o encorajaria a passar algum tempo lendo as resenhas, reclamações, etc. no link (WHT). Há um monte de histórias de terror lá (incluindo algumas das minhas), mas o volume é alto o suficiente para que você possa ter uma boa aparência nas suas opções. Os fóruns são em sua maioria de língua inglesa, com bastante representação no Reino Unido, então você não deve ter muita dificuldade em encontrar um provedor em seu próprio país.
Além disso, um dos sub-fóruns da WHT é inteiramente dedicado a ofertas de provedores de hospedagem. Você encontrará códigos de cupom para descontos, ou outras ofertas especiais, etc.
Na minha opinião, o EC2 da Amazon não funcionaria muito bem para você. (Todo o respeito ao outro cartaz que sugeriu isso.) EC2 é um serviço muito "faça você mesmo". Na minha experiência, é preciso ter mais conhecimento técnico para obter uma instância do EC2 em execução do que uma instância do VPS não gerenciada, já que a maioria dos provedores de VPS tem imagens prontas para uso com painéis de controle de hospedagem comuns, etc. pré-instalados.
Na verdade, sugiro que você considere se deseja gastar o dinheiro em um plano de hospedagem gerenciado. A maioria dos provedores de VPS tem algum tipo de opção gerenciada de serviço completo. Se você não tiver certeza de que pode gerenciar a configuração e a execução de seu próprio servidor, o suporte extra poderá valer a pena.