How to efficiently compute the most isolated point?
Use any algorithm for all nearest neighbors; then you can trivially solve your problem.  Such an algorithm finds, for each data point, its nearest neighbor.  The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan.

Apparently all nearest neighbors can be found in $O(n \log n)$ time; see the references on Wikipedia.  Or, if you want something to implement, take any data structure for nearest neighbors, and for each point $p$, find its nearest neighbor.