I’ve been very pleased with bytemark over a number of years. Their offerings are all VPS or dedicated boxes, so again you need some knowledge of server management. Their support is excellent and their control panel looks good, though I’ve never used that.

Service-wise I’ve also had good experiences with slicehost, but I’ve never really needed to contact their support department so can’t vouch for it.