On Saturday, just before going out, I purchased a VPS from New Zealand-based RimuHosting. A large part of the reason I decided to go with them was the testimonials from many of their customers about their amazing support, including praise from Ethan Zuckerman and Cheah Chu Yeow. My shortlist included Slicehost, but I decided against them because of their lack of DNS and of any type of money back guarantee. It was really tempting to choose them, but I figured that it was far safer to go with a hosting company that was well-known and respected - especially since I feel a bit like I am venturing into the unknown.
So far, I have gotten mail working. Once I finish configuring MySQL, I will export the contents of this blog and then change the nameserver to point at RimuHosting instead of Dreamhost. Theoretically, there should be no interruption in service (unless you happen to be interested in my Gregarius installation, or are subscribed to a mailing list hosted here).
UPDATE: The nameservers have switched successfully. Except for a bit of trouble with mysqld, things seem to be working - at least blogwise. Going to restart just to make sure.