Google was 97% accurate, at $4 per 1000 requests. Mapbox was 95% accurate, at $.50 per 1000 requests. TomTom was 73% accurate, at $.42 per 1000 requests. Location IQ (one of many providers simply running the open-source Nominatim project) was 12% accurate, at $.03 per 1000 requests.
To be fair to Location IQ / Nominatim, they had the right street the vast majority of the time, but were usually wrong about house number due to interpolating between address boundaries at cross streets defined in Census Data. If you need exact addresses, Nominatim probably isn't for you, but if you need a general location, it might work fine.
Also - this was one county of test data, so take it with a grain of salt.
Nevertheless, it gave us confidence that we could move away from the Google APIs, save 90% of our costs, and still have a high level of accuracy.