Media Temple Grid Server had uncomfortably high latency for me. Really terrible latency, in fact.

Go VPS and never look back: Slicehost.com (best service/documentation/been on the same virtualization architecture longer than linode) or linode.com (also very highly recommended and slightly cheaper than slicehost)