Я бы тоже советовал поискать в Европе -- физически близко, а цена может значительно отличаться (ну и качество)
Если сайтов достаточно много, то рассмотрите вариант выделенного сервера. У немцев (hetzner.de) неплохие цены, например. ~$80 вполне приемлемую конфигурацию можно взять.
VPS все-таки лотерея, тот же shared, только сам админишь