If you’re interested, Magento runs absolutely fine on our Shared Hosting. Our prices are competetive if you want to browse our site - http://www.nublue.co.uk/shared_hosting/ - and there is a link to our demo site in our signature if you want to have a look at the performance (it’s running on the same service you would be on, so it’s a very accurate indication).
I’m not getting paid to say this (!) - my experience with NUBlue has been good so far. I’ve only been with them a couple of weeks so early days, but their customer service is excellent, and when you ring up I get the feeling they have a good understanding of the technologies.