I’ve been a happy customer of Serverbeach for quite a few years now. Really, those guys are amazing.
Unfortunately, we use CPanel heavily, and that only works on Redhat-based distros, so I can’t benefit from apt’s magic.
I was pleasantly surprised when I spotted a how-to-install-ubuntu-remotely post on their blog today.

Does this mean that they will start to provide servers with Ubuntu preinstalled?
I sure hope so.

Incidentally, I highly recommend them, and, if you sign up, you can punch in my referrer code (TTER8PAF7S) and we both get heavy discounts on the servers