I’ve hosted sites on dreamhost, mediatemple and linode all with ease.
It somewhat depends on what your client is looking for and the pros and cons of each.
To me: dreamhost is quality hosting, but I don’t really like the cpanel interface that it uses and has decent customer support; Mediatemple has good customer support and a great interface for web admin type stuff but they have a more downtime than other hosts; Linode is affordable, has lots of space, very reliable but doesn’t have any web admin interface and requires you to setup the server yourself.
I typically go with Mediatemple or linode, but again its really what works best for you client. As for “improved EE service”, I’m not aware of anything specially any of those hosts do to optimize or improve EE sites in anyway. As far as I know, EngineHosting is the only one that claims that.