What I do is not look for the "best", but keep scaling 10x. So start with targeting 1,000 users, then 10,000, then 100,000 and so on.

Parse is awesome to start with at that 10,000 user mark. Parse seems to scale its costs poorly though.

Past the smaller scale you have a lot of choices. Azure. AWS. Firebase. IBM's thing. All have their pros and cons.