Check out this page for some deals: http://reviews.cnet.com/Basic_hosting/7026-6541_7-0.html?tag=tool1
You need to look for a Linux hosting provide though some Windows provider will have php/mysql option also but most if not all Linux providers will be able to accomodate your needs.
currently i am using godaddys free hosting, but i am running into problems running some of the php scripts that will run the majority of the site. Godady claims its the software and not them.
he site im going to host is just a family website that will have minimal vistors and will be password protected. What i need to run my scripts:
PHP version greater than 4.3.0
MySQL enabled in PHP
Safe mode disabled
File uploads enabled
GD libraries installed
PHP can write to the filesystem
i like godaddys priceing and would like the stay in the same ball park.