Digital Ocean just had some really great performance reviews on HN the other day and they are $5/mo for the minimum tier.
I was paying $29.99 (about 31 with tax) for a 768MB RAM box with 2.3Ghz cpu and 4 cores, 36GB storage and 300GB transfer with an additional $7.95 for backup ... so $40 all together. That eats a chunk of the $100/mo I make off my very small rails app.
For $20 ... I get 2.1ghz 2 core cpu, 2GB of RAM, 30GB storage (SSD btw), 3TB transfer with backups thrown in for free. So I save an extra $20 a month ... but if everything goes well, I'll probably shell out the extra $20 to get a 4GB box if the next 6 months with Digital Ocean go well just so I can be with in a better server neighborhood.