You could take the "center of mass" average of all corners on the plane (a new point which is at average x and the average y coordinate of all corners), then take the corner of each rectangle that is closest to that center of mass point. After your initial calculation of the center of mass, you would only need to run a single calculation for each corner.
If either rectangles happen to have more than one point that are equally distant from the overall center of mass then you would need to ensure you choose from among the tied points the two (one from each rectangle) that are closest to each other, and in this case you could just do the n^2'ed thing (although if we are dealing with convex polygons, such as rectangles, there could only be a max of 2 ties per polygon, so at this step there would only ever be an additional 2 or 4 calculations - depending on if one or both polygons contained ties).
This algorithm would scale very well (O(n)) for any two convex polygons each containing any number of corners (and their own center of mass equally distant from each corner they contain, like rectangles and all regular polygons), if that matters.
Ultimately, if you are always dealing with rectangles then you would need to decide whether or not the reduced computation time is worth the extra coding and testing of whatever optimized algorithm you go with.