The good news is that you can do it for NYC using OpenAddresses data. We published two pieces about how to geocode more generally:
https://www.nettoolkit.com/geo/the-basics-of-geocoding
https://www.nettoolkit.com/geo/adventures-in-address-parsing
It turns out that geocoding has been a much bigger project than we anticipated, but we offer the service very inexpensively. Let me know if you have any questions.