I have a linux VPS with Namesco, which has been really good. Just had to make a tweak in the .htaccess file to push up the memory limit, but other than that I've had no problems and I've got three live sites + 2 under construction running fine on it.

Obviously there is a bit of an upfront cost there, but its worthwhile as it means your site isn't on a server with hundreds of others, and you have full control, unlimited mySQL dbs etc.