Eu sugiro o Amazon AWS. Especialmente com a nova oferta "free tier", você pode executar um grupo surpreendentemente poderoso de sistemas a baixo custo e ter controle total sobre todos os aspectos de sua configuração.
Quanto ao DNS, tudo o que você precisa fazer é alterar seus registros DNS para apontar para seus novos servidores - ou você também quer mudar seu provedor de DNS?