Also, I saw a really cool presentation on the Azure platform. It supports push notifications, and even has a multiplatform template generator. https://azure.microsoft.com/en-us/services/app-service/mobil...
Both platforms feature a database and authentication.
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.
You might want to look at this:
http://www.kinvey.com/blog/3652/the-evolving-enterprise-back...
(the infographic on the blog)
If you need to spin-up notifications support quickly, Parse is pretty good. You can roll your own, but Parse is free until you get big.