Which web server, hosting company and platform is the best for directory or classified?

You requirements are truly minimalistic. It's very easy to satisfy them. You will be able to find cheep and acceptable hosting, may be even free of charge, however not so likely. It looks like your only essential requirement is PHP, which is currently available in nearly 100% hosting providers, so you need to pay attention to some more.

Don't fall into anything "easy" or "automatic", such as "site builders". They are acceptable, but if they are suggested as an essential selling point, it is a good sign than the hosting owners are oriented to serve the lamers, so it's very likely that the hosting is very bad in essential characteristics. You need good uptime and performance, decent disk space. Is you don't need ASP.NET, select hosting based on Apache. Make sure you can get some number of sub-domains which is sufficient for your current and future need. Of course, the site deployment should be based on FTP. You should have a Wen-based control panel (Plesk, cPanel or something); make sure you can control all essential administrative options, such as protected directories, sub-domains, e-mails, passwords, etc. Make sure you can work through HTTPS with the control panel — administrative access is too critical for your safety to risk it. It's very good to have control over local .htaccess files, error pages, etc. Usually you can get a free domain name with the purchase of the hosting plan.

I cannot recommend any particular hosting provider and do not to recommend any of them, even the one I use. You have to Google to find some candidates for yourself. Now, how to know which is reliable enough? This is a problem, but you have to look at hosting comparison sites and learn about reputation points and customers' feedback.

This way, I'm coming to a most important advice on how to protect yourself from unreliable providers and not returned money in case of problems: always select those offering free trial period (which is often unlimited). Free-of-charge hosting (be careful: should always be free from advertizement!) is actually a sign of good quality. Well-established high-quality hosting providers usually provide free hosting as a way to get paying clients. You develop and deploy first version of your site using a free-of-charge plan, work for a while to estimate the quality and later either abandon it (providers clean might clean it up after some period of inactivity) and go to another provider, or sign for a payment-based plan, pay for a year or two (for better rate) and get extra resources/features immediately.

—SA