Tipo de hospedagem que possa me atender

Boa tarde meus amigos.

Minha duvida é a seguinte: Estou com um projeto de um site de rede social (Não criei a rede social, apenas comprei um script e modifiquei), essa rede social e exclusiva da minha cidade que tem mais ou menos 500 mil habitantes, é claro que também poderá receber usuários de outras cidades/estados, minha preocupação e em relação a hospedagem suportar o tráfego e o armazenamento dos videos e fotos publicadas pelos membros do site.

Sei que todos vão me indicar um dedicado robusto, mas de começo não quero investir tanto, até porque não sei se vão receber bem a rede social, afinal temos o facebook, estou apostando na exclusividade de ser uma rede social com o nome da cidade e outras coisas.

Um bom vps da pra começar?