I run multiple servers off of rackspace's cloud, at their lowest tier which costs 1.5 cents per hour, or roughly $11.00/mo +bandwidth. It's such a cheap solution and is more than sufficient for the hosting that I use them for. They've surpassed expectations from day one.

Used to use webfaction, which was pretty solid too, but moved away due to some flexibility issues.