The main problem with cheap hosting companies is that they use more or less one-click installers like cpanel or plesk. They generally don't upgrade all too quickly to newer technologies or versions, both on the hosting company side as the control panel provider. I'm guessing it's more of a "if it ain't broke, don't fix it" thing than something else.
We've had our fair share of horror experiences in the past, so I totally get the dilemma you are facing. I do want to add that even getting a Rails app properly running, even when you're talking about a 2.3 app, will probably yield another round of frustrations. Support tends to be totally ignorant on Rails apps and you basically get a copy-paste section of the cpanel manual.
I'm quite sure there are some fixed price hosting companies out there, http://hostingrails.com/sharedhosting springs to mind, but they are also stuck on 3.0 it seems (byebye asset pipeline etc).
Out of curiosity, what kind of fuss are you talking about? Ease of deployment or having to advise someone to switch hosting providers?
Peter De Berdt