Linode is $5/mo. and I got a $50 credit for just being at a software conference; I also don't think that expires (which is good because I'm not planning on using that credit atm). That's 10 months of free service.

It's also pretty barebones in terms of upsold services, but apparently the customer support is pretty top-notch. I'd take a look at it.