I've had good experiences with Ramnode and BuyVM, and in the distant past, also Linode.

Edit: Ramnode has competent support without a lot of time wasted with "cannon fodder" / tier 1 if you have a problem, sounds like that may be an asset for you. They are definitely oriented toward customers who know what they're doing.