I'd recommend Digital Ocean, I've been using them for about 5 months now and they have been pretty good. Smooth running, fast machine, and they start at $5 a month (which is what I'm on). For Rails you might want to go for a $10 a month one, but it won't matter too much.

Here's a (referral) link: https://www.digitalocean.com/?refcode=09e94b0118a3

Although I have given my referral link, my recommendation holds whether you choose to go for them or not.