I love seeing all the great comments in here about the different APIs and the features they do and don't offer, but I want to point out that the underlying data for addresses is incredibly hard to find. The reason the commercial geocoding providers won't let you store their data is because they're worried you'll store enough data to build your own geocoder.

To help with this, a group of folks (including me) started OpenAddresses (https://openaddresses.io/ and https://github.com/openaddresses/openaddresses/) with the goal of finding every open address dataset in the world. We produce a zip file with 100M's of addresses that several of the APIs mentioned in this thread use as a major part of their dataset. We've been going for well over 10 years now, but it would be great to have more eyes looking for more address sources. Check us out!