Gustavo,
Antes de contratar um VPS, saiba que isso traz inúmeras responsabilidades de você nao teria ao utilizar uma hospedagem compartilhada.
A não ser que contrate um VPS gerenciado, você vai ter que se preocupar com cada questão de segurança do servidor.
Alémm também as configurações do servidor web que utilizar. Não é só instalar tudo e sair usando.. Se fizer isso vai acabar tendo problemas novamente.
Já fui cliente de diversas empresas de hospedagem e fico receoso em recomendar nomes.. Acho que o que funciona para um, nao necessariamente funciona para os outros..
Mas sinceramente, em um caso de tantos acessos simultaneos, acredito que você deveria pegar as informações de consumo atual do teu host e de repente partir para um host compartilhado em uma empresa de grande porte (provavelmente vou citar nomes que alguns aqui nao devem gostar, mas ok), tal como kinghost, godaddy, uol, locaweb, etc..
Na pior das hipoteses eles vão oferecer um plano (ou cloud) mais adequado ao site..