Generalised data science approach to astronomical catalogue cross-match
The generalised algorithm I was looking for was a k-dimensional tree, a space-partitioning data structure which is commonly used in nearest neighbour searches. There are implementations in scipy.spatial (KDTree and the faster cKDTree) and in sklearn.neighbours (also called KDTree).

These are the underlying engines of the Astropy and AstroML catalogue cross match methods, though for my specific use case I required the functionality of the k-d tree itself. The KDTree allows one to search in any number of dimensions, though these need to be scaled (by std dev) if they are different properties.

In some preliminary testing I found this to be over 100 times faster than the C3 algorithm I linked above for my use case. It takes around 10 secs to pick, for 85K sources, the nearest neighbour from a catalogue of 1.4M sources (when searching in 4 dimensions: 2D position, flux and size)