Hola!
Creo que por lo que mencionas, efectivamente, un VPS será una buena opción para ti, conozco un par de empresas hispanas con representantes en este foro que podrías mirar:
http://ideasmultiples.com/ http://allinhosting.com/
Aclaro que no las recomiendo personalmente porque no he usado sus servicios, solo he oído buenas críticas de ellas y he visto que sus participantes en este foro demuestran ser personas con buen conocimiento.
Saludos,