I am considering replacement of Google Maps with Open Street Maps and the Leaflet JS API. Does the Leaflet JS API provide a Geocoding service?
Leaflet itself does not provide geocoding services, but you can look at Nominatim for example. http://wiki.openstreetmap.org/wiki/Nominatim
I found a Leaflet plugin that works great. It's a Bing geocoder which you'll need your own key for https://github.com/sa3m/leaflet-control-bing-geocoder
I have fallen in love with the Mapbox Geocoding API -- they do a great job of aggregating a lot of data sources that would be a pain for me to aggregate on my own. I found it to do a better job of reverse-geocoding than Nominatim. If I ever needed to build out my own geocoder, Nominatim would be a great place to start, but for most projects it feels to me like overkill.