I will kinda gloss over technical details for now, feel free to ask for clarifications.

I suppose that you want to answer queries of type "What is the closest rectangle to this point?" in less than O(n) time. Now shortest distance from the point P to the rectangle is the shortest distance from the P to one of its sides. The shortest distance from P to the segment AB is either min (|PA|, |PB|) or length of perpendicular from P towards AB, if it lands on the segment AB of course.

Now, let's see which case actually happens for rectangle, which is the closest to the point P. Dealing with second case is simple: we just need to cast 4 rays in all coordinate directions from the point P, for each ray find the first rectangle they intersect and remin answer with this rectangles (note that because all rectangles are axis-parrallel, all perpendiculars to the sides are axis-parallel too). To deal with the first case, you need to find the closest point to P among the corners of rectangles: in general, such a problem can be solved with Voronoi diagram (and I am pretty sure that there is not anything significantly simplier in general case), in your case there may be some simpler solution, but I can't see it for now.

Total time: precalculation (for Voronoi diagram), per query. It seems that you need something like a persistent treap to answer queries online, but offline you can do a scanline with set to handle both described cases (after you built the Voronoi diagram, of course)).