I started out on basic shared hosting then moved to VPS then to dedicated, then to two servers dedicated with CDN.
My suggestion is to pay as little for hosting as possible until you grow. Dont try for an overkill on hosting it will only frustrate you because you will be broke in the beginning.