Hi Curt,
I see two considerations for hosting: budget and technical ability. For example, using Media Temple's DV service is going to be inexpensive ($50/mo to start out), scalable, and simple to setup. Compare that to RackSpace Cloud Servers (http://www.rackspace.com/cloud/cloud_hosting_products/server...), which is even less expensive up front ($12 a month or so), but from what I understand requires a bit more technical ability to setup/configure the server (please correct me if I'm wrong folks, as I haven't used Cloud Servers yet, just talked w/ people that have). Either option will easily scale.
There are many other options, but don't want to provide "advice" when I haven't used solutions like http://www.voxel.net/ or others.
Other considerations - is this going to be a global audience? If so, look into using a CDN. You could use MT's CDN (http://mediatemple.net/webhosting/procdn/) if you use the DV service since it is currently only available for MT customers.
I don't have much experience with ecommerce platforms, but your needs seem pretty basic and should be covered by any opensource option out there. Can you think of anything specific that you'll need in the longterm spec - multiple pricing options for consumers or wholesalers, discount codes, etc.?
Good luck with your startup!