If I might make a selfish plug, I use
DreamHost and they've been decent as an ultra-cheap hoster. Decent web-based tools, large quotas, decent support, and, yes, MySQL. They cost between $6 and $11, depending on how far in advanced you pay, and they have a deal going where you can get $110 off any year-long purchase (so a one-year purchase is more-or-less free). The code is on their front page.
And if you sign up through
here, I get a kickback
