I'd had servers at a few different places and for managed VPS I would go with
http://www.servint.net/
Been getting all my new VPS there. The support is amazing fast. I locked myself out of my own firewall yesterday like a moron and they white listed me in under 2 mins.
If you need cheap shared hosing I can't really help you. No experience.