[tdj]

I strongly recommend Gisgraphy - http://www.gisgraphy.com/ [not affiliated, just a happy user].

They offer both SaaS, as well as a simple way to deploy the whole thing and run a local (reverse-) geocoding server. It does take a few days to build the GeoNames + OpenStreetMap index though. I run it locally for mapping coordinates to cities and it runs quite decently, a 2-core 2GB Linux VM running PostgreSQL gets me about 80-100 queries/s. It has a nice JSON API so it shouldn't be too hard using it from iOS.

[morsch]

That strikes me as a fairly low number of requests per second for powerful dedicated hardware. Am I way off here? Is the problem much harder than I think it is?