[obituary_latte]

+1 here for Rackspace mostly due to their excellent support. They seem to have a dedicated WP offering[0].

Have also heard mostly good things about Linode (exception[1]), but don't have personal experience with them.

[0]http://www.rackspace.com/cloud/sites/web-hosting/wordpress/

[1]https://blog.linode.com/2013/04/16/security-incident-update/