For the benefit of others considering a hosting environment I am currently using Dreamhost. The interface is a little bit slow, but not sufficiently so to be really annoying. The public website, with partial caching, is fairly zippy but sometimes suffers from a 'wake up' period in that the site is faster after being woken up by the first hit on it for a while.
The main issue I have had is image conversion due to memory restrictions. PHP scripts appear to be restricted to 90M, whereas my local development box is 128M - this difference unfortunately appears crucial as I am often running out of memory resizing images. The work around is to change the template to show 1 pic, 2 pics etc until all the thumbnails are calculated but it is not ideal