HI! Sounds like you have a lot of work ahead of you.

I would say write it in the language you are most familiar with. If you feel comfortable in Java, then it's a great choice. NodeJS is also a very popular choice for API servers, and Python has two great, slim tools in Flask and Eve: http://flask.pocoo.org/ and http://python-eve.org/.

Also, PHP 7 just came out and it's been thoroughly vetted; even if it's not battle-tested yet, it's way faster than previous versions and worth the investment if you are familiar with php.

As for storage, it really depends on your data structure, but SQL fits most apps really well, and there is good support for it in cloud hosting.

For hosting, I would look at AWS and Google. AWS offers more robust storage options with RDS and DynamoDB, but I bet Google is catching up fast. Both are very good options and offer great scalability, but are more complex to setup than a pair of VPSes.

If you're in the market for a VPS, Linode has a managed Load Balancer service that's easy to setup and you can get a good HA setup for webservers with minimal effort.

I guess the storage part depends very much on your data. Feel free to ring me up, I'd be happy to explore this further.