In search for public (and fast and low cost) geocoding services, I’ve run into Texas A&M GeoServices.
I have only tested their reverse geocoding service and it was all of the three above. It took no more than a cup of coffee to provide addresses given latitude and longitude and information added looks very promising.
They even have a partnering program that could minimize the expense of using said service. Neat! Expect upcoming posts to attribute all geo data to them as so: