I can second GeoNames. Sometimes it's hard to beat free. We take a couple files from their dump[1] (primarily the city data) and import into a database. We can then geolocate a lat/long to the closest city.

1. http://download.geonames.org/export/dump/

I'm using it for a photo app (I only need town/city level granularity), and it works well for my needs. Note that the dataset is based upon populated places though, so YMMV if you need to lookup somewhere in the middle of nowhere.

Here is a JavaScript library I wrote for it, along with some scripts for munging the GeoNames dataset:

https://github.com/lucaspiller/offline-geocoder/

If you need higher granularity, take a look at this OSM project:

https://github.com/twain47/Nominatim/

I was turned off by their blurp that their US zip codes database contains only 21k zips out of 41.5k. Are they sufficiently complete for small towns?

The incomplete zips (for at least one database I've read about) come from corporate or industrial areas where not many people actually live.

Officially US zip codes are just collections of addresses, they don't necessarily correspond to areas.

I think most free datasets are probably just the areas that Census derived for TIGER (or at the very least, rely heavily on that data).