No me gusta mucho recomendar
Lo mejor es no contratar las grandes empresas tipo 1y1, hostalia, webfusion, strato, hostgator, godaddy... etc
Luego fijate que cumplan con el estandar de contratación que siempre a reinado internet y que estas grandes lo quieren abolir: cuando dejas de pagar se cancela el servicio y ya está, no hay reclamación por impago
Las pequeñas son mejores, pero si son revendedoras deben incluir la administración sino siempre será más económico la matriz.
Te pongo mi lista, que no quiere decir que no haya más
Cloud
https://www.digitalocean.com/ https://www.linode.com/ http://aws.amazon.com/es/ http://www.rackspace.com/es/
No administrados escalables
https://ginernet.com/vps-ssd.php http://www.ovh.es/vps/vps-cloud.xml
Administrados
http://www.mundiserver.com/vps-hosting.php https://gigas.com/cloud-vps https://cubenode.com/cart.php?gid=1 https://ginernet.com/vps-administrado.php