Optimizing a Proximity-based Store Location Search on a Shared Web Host?

What precision do you need? if it’s a state/national wide search maybe you could do a lat-lon to zip lookup and have precomputed distance from zip area to zip area of the restaurant. If you need accurate distances that won’t be a good option.

You should look into a Geohash solution, in the Wikipedia article there is a link to a PHP library to encode decode lat long to geohashs.

Here you have a good article explaining why and how they use it in Google App Engine (Python code but easy to follow.) Because of the need to use geohash in GAE you can find some good python libraries and examples.

As this blog post explains, the advantage of using geohashes is that you can create an index on the MySQL table on that field.