Do not go with lunarpages, I am a former client and I can tell you they are awful. Slow servers and non-existent support (They don't even have a toll-free number)

I believe Dedicated Servers | Managed Dedicated Servers | Web Hosting | VPS | Liquid Web lets you do all that you mentioned

__________________