Hola,
te recomiendo visitar
http://www.lowendbox.com/
En caso de nunca haber manejado un vps o servidor te recomendaria que sea un servicio "managed", otro punto a tener en cuenta es que el servicio sea escalable, es decir que te permita ir ampliando el espacio y la memoria en caso de que lo necesites.