You can certainly start out on shared hosting and then grow as needed into a VPS or dedicated. Ask the companies that you're talking to if they can easily migrate you from shared hosting to dedicated solutions? Some hosts would force you to set up from scratch on an upgrade, which of course could bring problems with PHP / MySQL versions, Apache configs, etc. Ideally, if you want to start small and upgrade, you'll want to deal with a provider that can help you make it as "plug and play" as possible.