The best hosting experiences I've had are with Linode, AWS and Rackspace. Linode for their brilliant custom control panel - a key differentiator between them and those running stock control panels. Rackspace for the support - if I need to speak to someone, someone will pick up the phone in 2 rings or answer a ticket in 15 minutes. AWS for the fine grained pricing and ability to scale up and down at will.

All of the above are leading or close to leading in their respective niche areas. Their innovations and key differentiators appeal to different types of customer, product and price range, neither which you have stated. It is difficult to give advice on this basis, are we advising how to innovate $x/month bargain hosting or $xx,xxx/month enterprise solutions?

I think you have to identify these clearly before proceeding.