Mod Note: Topic moved to the Hosting & Performance section.
The type of hosting service to go with will depend on a few factors, mainly your budget and how fast do you think you will achieve mass adoption.
Going with a Magento focused company is a good start as their environment will be specially tuned for Magento and their support may be more familiar with Magento which will make your life much easier.
You can consider starting with a smaller plan since you are just starting out but make sure that the company you go with have smooth upgrade paths so that you can easily scale up as your store grows with the least hassle possible.
If you have the time to test each provider out, most of them should have some form of trial or money back guarantee so you can give them a try for a short period of time and get a refund if you are unhappy so you are able to make a more informed decision and you lose nothing but time. 