Pues Hostgator no es tan mal, eso si, hacen overselling y eso puede afectar el rendimiento, pero si dices que no tiene muchas visitas quizá no sea el hosting lo que está mal, quizá su sitio no esta optimizado (mala programación, bases de datos no optimizadas, joomla).
Y no afecta de manera significativa si el servidor está en EUA o en España, claro si no se hacer muchas descargas, de hecho yo utilice por un tiempo una VPN en Ucrania y yo estoy en México, la verdad es que casi no se notaba la diferencia.
VPS no creo que sea la opción por el tráfico que tiene.
Saludos