One of my clients signed up with Dellhost (Dell's hosting service), attracted, no-doubt, by Dell's big-name reputation, and it turned out to be quite an unpleasant experience.
I ran up against a bunch of pretty clueless and very stuck up sysadmins who were trying to tell me through many HTML formatted (ick!) mails that though theoretically the server was mine and I could do what I wanted with it, in practice if I tried to wipe out their RH install and put in Debian, then:
1. It was not allowed and they would not let me do it.
2. If I tried I would probably fuck it up 'cos they had custom ethernet hardware and then I'd have to pay them $150 per hour to reinstall RH.
3. If I did manage it they would not support the box except to restore it to factory defaults and wipe out my OS and all my data.
I ignored them and did it anyway and then I got a mail from them complaining that I'd blocked their backdoor sysadmin access port and telling us that now they had no way to take backups (which we had not asked them to take) and basically complaining that we'd shut them out of the server and that they would reboot it into single user mode to get root on it. I didn't even grace all this shit with a reply.
There are a whole bunch of hosting services but I'd try to avoid things like DellHost or Gateway-Hosting (though I haven't tried this one) where the company's primary biz is making boxes. They will tend to have clueless sysadmins.
As I admin a few boxes from halfway around the globe, I am always on the watch for cool services like a remote console and remote hard reboot features. I heard of a company offering these but I lost the URL. I'd love to have services like that.