I like slicehost for a number of reasons, but you have to be willing to use a command line because there is no GUI unless you install one (because you're getting a virtual server with full root access).
I currently use them, for the Rosegarden website among others (wonder whether I'll regret that link -- that's running on their most basic VPS package). The connectivity appears good and I like the command-line-only approach.
What's not so good is that they only offer 64-bit distros with relatively little RAM for the price, so you can run out very easily (or pay a lot).
Really though, whatever you do your best approach to ensure you can bring up the site anywhere at short notice without losing a significant amount of data. Run your own backups, manage the DNS elsewhere, and so on. If you can afford it, maintain another ready copy of the site at a different provider.