I've been using Webfaction, and I'm pretty happy with it. It's about $10 a month, you get SSH access into your box, and they have really good customer/technical support. http://webfaction.com
And, as you'll become better at configuring your stuff and will want more control over all the nifty details, you could then switch to a vps.
Also, don't forget that Heroku now support more platform.. in fact, everything python is supported, but the platform is strong enough to support anything.. even if it's not as userfriendly as the ruby or python way.