Enough with these lousy advertisements. The best PHP/MySQL hosts are those most haven't heard about, because they don't invest everything in marketing and let their customers down with bad connectivity and support. Go with the one without flashy websites and adds on!! But those that support such thing as Perl, PHP, MySQL, Procmail and crontab, and have muliple OC-3s, and charge around $25 for 100MB of disk space and 10GB of transfer.
I've tried CIhost, the 1GB package for $20/month, but the MySQL database is limited to 25MB and they rip you off with adds on and server downtime, poor connectivity and marketing arrogance.
Luckily I found the best one by chance but must keep it low key...Good luck on the search, try looking up domain info when you come accross a speedy dynamic web site!!