Give us a little more info about your requirements - how many MySQL databases you plan to host and how big approximately would each one of them be? If they would be fairly small then almost any shared account would suffice. VPS would be a little bit of overkill in such a case.