Well, you're not posting in a marketing area - so lots of peoples' advice may not be posted. On the other hand, you won't be inundated with hosting offers
If I were in your situation, I would first look for a host that had all the necessary programming elements I wanted on a shared hosting account, and all other available options (database usages, permissions, what have you.) I'd develop the application but not make it available to anyone while it was being built. Then when I was ready to start having any level of traffic, even a limited beta test, I'd make sure I knew of a host that offered larger shared hosting options or even a VPS where I was one of very few clients on the server. Then I'd keep my eye on disk space/bandwidth usage, stay ahead of the growth curve by upgrading before I hit my disk space/bandwidth limit, and start doing research for a dedicated server provider for when *that* move became necessary.
Ideally, if you can find a host that offers all of these stages - shared, VPS, dedicated - then the moves should go smooth as milk.
Just make sure you do your own regular backups, even when you get to a dedicated server. Backups have a way of failing at the most inconvenient times...