Eu ia responder praticamente isso que você postou.
Começar em uma VPS simples, PG para mensageria também, e mesmo no futuro quando as coisas derem certo, dá para deixar parte da aplicação ainda nesse ambiente mais simples com os CRUDs da vida e colocar apenas os serviços mais pesados em ambientes mais poderosos.