Re: Minimum Needs in a Host
MySQL 4.0 ( I would look for 5.x for futureproofing)
PHP 4.2 ( Again, I would look for 5.x here)
Apache with mod_rewrite
That’s all your host needs to offer. I would expect to pay less than $10/month. It might be a lot less if the host does not offer shell access (just FTP.)