To clarify why, the landscape for that is fairly grim right now. GeoNames (http://www.geonames.org) seems to be the best that i've evaluated thus far. It'll cost you at scale (not much), but it's international and can find nearby neighborhoods/cities. Google requires you to display their information on one of their maps if you use them to geocode or reverse geocode.
Question for iOS devs out there: how are you finding nearby cities in your app from a lat/lng point? (is even asking this against the ios rules?) Right now I am using geonames and the results are pretty decent. Works for now!
There is a VM to play around as well: http://www.openstreetmap.org/user/AndrewBuck/diary/17698
Also there is Mapquest's API which uses this: http://open.mapquestapi.com/geocoding/
There are some numbers available at http://wiki.openstreetmap.org/wiki/Osm2pgsql/benchmarks (eg getting it into EC2 in a day for ~30USD). Even just a week would be a pessimistic estimate.
I guess if all you want is geocoding, you could exclude a lot of data before importing it. Eg landuses without names, lots of single nodes that have nothing to do with addresses, etc.
I am not trying to fear monger, I am just trying to say "hey, BTW unless you have a big hardware budget, you might want to just pay a third party".
Over 5 years old, API is still available:
Easter egg: All the little pixel characters on the homepage are members of the dev team. I'm the one on the left in blue jeans and a dotted shirt :)
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.
The basic gist of it: Init a CLLocation object with a lat/long (probably pulled from the device GPS or a map dropped pin) and then call CLGeocoder's reverseGeocodeLocationInitialize and it'll return a CLPlacemark, which contains the approximate address.
To just find nearby cities from a lat/long though, you probably don't need to reverse lookup the address, it's probably easier to use something like MaxMind's free database which would give you the lat/long of cities, host it either locally on the device (a subset, obv) or on your server and then just use math to put some coordinate min/max bounds on your query to find city names nearby.
The best replacement I found when going over Google's limits was Yahoo's PlaceFinder.
I integrated Google, GeoNames and Yahoo in a npm module: