" this is very slow"
Have you measured it?
Something as trivial as walking an array and comparing two ints isn't that slow.
A possible bottleneck (often saw) is to load the sound when the point is hit. It depends if you have 2000 different sounds, you might not be able to load all of them at once. You might have a problem of playing lot of sounds simultaneously, though.

" it would iterate 4000 times per agent each frame"
For 2000 coordinates? Why two loops? Do the checks in the same loop.
Some algorithms can help too, like sorting the arrays by x, then using a binary search on it, and for the given x, check only the corresponding y. In any case, you want the coordinates in a array of PVectors to maintain the consistency.
And don't forget to quit the loop as soon as one result is found.

Note: for performance on lot of agents in 2D (or 3D), there are algorithms like Quadtree (check Wikipedia, search the forum), aka. spatial partitioning. There might be a library about that, unless that's just some code fragment in the old forum?

I ran across this today:
http://www.soi.city.ac.uk/~jwo/processing/ants1/

hashgrid is just what you're looking for, I think

When you say you "have an image", you presumably mean it's static?  In which case you may find this demo useful  ;)
Actually I'm pretty sure this is one of the posts that prompted me to put it together.