Tech radar did a review of best VPS 2018 this week that might give you some providers to review.
https://www.techradar.com/uk/news/the-best-vps-hosting-of-2018
We can't give you a concrete answer as best is subjective to your start-ups needs which only you know.
The only advise I can give is that AWS, GCP, Azure can be complex and although they can seem relatively cheap you can find that you can accidently cost a lot by mistake. There are horror stories everywhere e.g.
https://www.reddit.com/r/aws/comments/4jdplq/charged_163537_after_accidentally_hitting_an_http
If you can get a fixed cost per month/year then you know your outlay upfront.
I would also look at your current capacity on shared hosting and you predicted growth to ensure the provider works now and in the near future.
Lastly, I would seriously consider splitting your applications to multiple servers rather than everything on the one server. If this server has an issue or need to perform maintenance ALL of you customers will be impacted. Putting all your eggs in one basket is rarely a good idea. The cost of two small servers is usually the same or less than one massive server.