I'll concur on ServerBeach and RackSpace (and not just because they include Webmin on all of their boxes). Great company with great service and reasonable (not cheap) prices.
For the slightly lower end, Joyent's Accelerators are a cool and cheap way to get a "dedicated" system (they run in Solaris Zones, which are, frankly quite a bit more reliable than Virtuozzo and vservers based systems), and the company is run by a bunch of really smart guys. And I swear I'm not just saying that because they include Virtualmin GPL on all of those virtual servers, or because they are upgrading to Virtualmin Professional on their TextDrive shared hosting systems as we speak. Or because I like them personally.
And just so you don't think I'm only recommending companies that use our software, The Planet is good and cheap, too. Very solid network and hardware. We've got a big Dell box with them that includes a remote terminal thingy that allows me to see the BIOS and all via a remote Java applet console. Very cool. They do not, however, offer any Virtualmin products on their boxes...that's a problem, of course. But I'm sure we'll remedy it soon enough.
I have a few boxes with Serverbeach and I think they're great. If you end up going with them, find a friend who uses serverbeach to give you a referral code. It'll give you and your friend $100 (I think) off their bill -- which can definitely help during the early bootstrap startup days.
If you have the money and really need hardcore service Rackspace is absolutely incredible.
One more vote for ServerBeach. They're a rare combination of competence and low cost. Haven't had any problems whatsoever. Definitely find a referral code before you signup. Otherwise use mine! 7XYHDMBU8A It's $100 discount for the new user and $250 for the referrer.
They worked well for ourdoings.com too. I've been using them for about 18 months. When I had a hardware failure (memory) they took care of it reasonably quickly.
They do have technical issues from time to time (including one that occurred recently), but so does everyone else, IMO. And they're much better about handling it quickly - and communicating to you what happened and how they're handling it.
For the slightly lower end, Joyent's Accelerators are a cool and cheap way to get a "dedicated" system (they run in Solaris Zones, which are, frankly quite a bit more reliable than Virtuozzo and vservers based systems), and the company is run by a bunch of really smart guys. And I swear I'm not just saying that because they include Virtualmin GPL on all of those virtual servers, or because they are upgrading to Virtualmin Professional on their TextDrive shared hosting systems as we speak. Or because I like them personally.
And just so you don't think I'm only recommending companies that use our software, The Planet is good and cheap, too. Very solid network and hardware. We've got a big Dell box with them that includes a remote terminal thingy that allows me to see the BIOS and all via a remote Java applet console. Very cool. They do not, however, offer any Virtualmin products on their boxes...that's a problem, of course. But I'm sure we'll remedy it soon enough.