How can I find the nearest point on the coast from an ocean location? Given some location of interest $X$ in a lake or in the ocean with known lat and lon, I'd like to find the lat and lon of the coastal location that is closest to $X$, as well as distance between the two points. Of course, once the lat and lon of the coastal point is found, it's straightforward to compute the distance. I know of this DistFromCoast dataset that has the distance to the nearest coastal point, but it does not provide the nearest coastal point itself.

Would anyone know of datasets, software, or algorithms that may help with my task?
There are public databases with the coastline in lon,lat format. You just need to find the point closest to your coordinates in that coastline. For that you need the formula of the distance between two lon,lat points on an ellipsoid. In this article you can find that and an idea of how to do it: 
Garcia-Castellanos, D., &amp; U. Lombardo, 2007. Poles of Inaccessibility: a calculation algorithm for the remotest places on Earth. Scott. Geogr. J., 123, 227-233. doi:10.1080/14702540801897809 
available here: https://web.archive.org/web/20140629230429/http://cuba.ija.csic.es/~danielgc/papers/Garcia-Castellanos,%20Lombardo,%202007,%20SGJ.pdf