As far as I know, Magento is not the easiest script to host. Quite a few hosts will probably steer you towards a VPS. Personally, I'd try to get feedback from other Magento users on the Magento forum www.magentocommerce.com/boards/
You can also try to use this search in Google: "site:www.magentocommerce.com/boards/ hosting" for a quick look at past topics that could help you.
One host that I know of to be specializing in application hosting, and Magento in particular, is Crucialwebhost, but I never used them myself. They're a small-mid sized company, something that comes with both advantages and disadvantages.