What data structure would help find nearby coordinates quickly?
Yes, you could you could do better than a naive approach - you could use a k-d tree data structure.

Clever implementations, such as sklearn k-d tree do the nearest neighbour lookup in O(log(n)) which, unless you have a high dimensional and sparse dataset, will work significantly faster than a naive O(n) approach.