Any host that has php and mysql. Unless you mean a host that can sustain heavy use of mysql queries then I would not go with cheap host. They might become unreliable, or boot you off their server saying your site using the mysql too much.
I have'nt had it happen yet although I have my anxieties. I know I'm going to have to move soon from my host any month now. 3 wordpress sites use alot alot mysql. You can try this cheap host 4.99USD a month Although I don't know thies hosts tend to crame hundreds of sites on one server. I looked on checker and they have 400 sites already on one server..haha
I have a assumption thies cheap hosts are actually just reseller hosts. Like a site buying a dedicated server with dreamhost then reselling it, packaging it as there own company. I guess you get what you pay for. If stieground is booting you off, then t35.com (the host I mentioned) will most likely not a good option. the same thing probably will happen. Why not just go straight to the source