Personally, I use Shyper, and I'm quite satisfied with them. 500 MB storage, 25 GB bandwidth, PHP, 3 MySQL-databases, cPanel, CGI-bin, Fantastico and more. This is the personal plan and that costs $6.95 pr. month. They also have a Pro plan that costs $9.95 and gives you a lot more. Uptime is good, and personally, I won't move somewhere else. Oh, by the way, you get free domain for life (or at least as long as you stay with Shyper).
There is also another place - Cliche. They will charge you £0.50 pr. month for 500 MB and 1 MySQL database. I don't know anything else about them, though.
I don't know if you will call this cheap or not, but I find the pricees to be quite reasonable. You'll have to check them out and decide for yourself.
For the sake of order: I'm not associated with any of the above mentioned providers in any way, other than that I have my account at Shyper.