Warning: Bad ideas may be ahead! Caveat lector!
A pretty reasonable technique would be to have a max awareness distance and first culling your list with a simple "in-rectangle" test (x,y) \in ((x-r),(y-r)),(x+r),(y+r)) before doing any kind of distance comparison. This is still O(n^2), but probably with a lower constant.
If you need better complexity you could maintain a quad-tree (think 2D equivalent of http://en.wikipedia.org/wiki/Octtree
) containing all the monsters/objects of interest and updating it whenever a monster moves. Since level size is fixed once a level is created you could also get away with a fixed-depth quad-tree. Then you'd only have to check the monsters/objects in rectangles adjacent to the rectangle of the object you're considering. This would give you O(n*m) where m is usually a lot smaller than n (obviously depending on general monster density).
A third option: Have each monster/object maintain a list of references to all other monsters, ordered by distance. Whenever a monster/object moves you can update this list appropriately. The update could use some sort of bubblesort-esque way to update the lists efficiently.
EDIT: Eh, there's actually a quadtree article at WP: http://en.wikipedia.org/wiki/Quadtree