I used to be on Site5 (just their normal shared hosting) but have since moved to Linode. There $19.95 VPS is extremely good value and fast enough to handle pretty active sites. Plus you get the advantage of being able to run ANYTHING on it
.
The only down side is that it is unmanaged hosting which means you need to do all the sys admin stuff yourself. I'm not convinced that cloud hosting providers offer that much advantage. Linode beats the crap out of the Amazon cloud in terms of speed.
In fact most cloud providers have poor IO performance which is generally bad for websites and cost significantly more than a decent VPS setup. You have to pay a lot for the premium cloud disk solutions (and I really mean a lot).