iOS's built in MapKit provides a reverse geocoding lookup API. It used to abstract away the Google geocoding API, but I'm not sure if iOS6 still relies on Google for that, I haven't looked into it.
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.
It hasn't relied on Google since iOS 5, when CLGeocoder was introduced. This is one reason why the new geocoding classes (versus the now deprecated MapKit ones, which used Google) are somewhat less accurate and absent entirely from certain countries.