I am using Engine Yard. Fantastic service and very snappy response time on the app. It feels the same as on my local machine.
Michael
Or, if you want something that's actually within your budget, try http://rimuhosting.com/ or check out the various plans described/collected at http://www.railshostinginfo.com/
-Rob
Rob Biedenharn http://agileconsultingllc.com Rob@AgileConsultingLLC.com
Check out http://www.slicehost.com very affordable, lot's of power. Should fit within your budget.
Nathan Garza