I would recommend using a Quad Tree. They allow you quickly and efficiently look up all objects in a given rectangular area. Here's the wiki article on them: http://en.wikipedia.org/wiki/Quadtree

And a shameless link to my own XNA Quad Tree project on SourceForge: http://sourceforge.net/projects/quadtree/

I would also maintain a list of all the large objects so that they can interact with everything regardless of distance.

I would recommend using a Quad Tree. They allow you quickly and efficiently look up all objects in an arbitrary rectangular area. Here's the wiki article on them: http://en.wikipedia.org/wiki/Quadtree

And a shameless link to my own XNA Quad Tree project on SourceForge: http://sourceforge.net/projects/quadtree/

I would also maintain a list of all the large objects so that they can interact with everything regardless of distance.