If you are just starting out i.e. validating the idea - go with the cheapest and the easiest option which allows you to get the site up and running in front of your users. If this means cheap web hosting (assume you have no experience with a VPS) - then so be it. If you have managed a VPS before, then start with the cheapest VPS (say prgmr or linode). You can always easily scale the VPS until you reach a point where you need a dedicated server.

Best to cross the scaling bridge only when you come to it.