Do you want a metric on rectangles? This means that $d(R_1,R_2)=0$ only if the rectangles $R_1$ and $R_2$ are completely identical (same size and location). Also it means that the triangle inequality is obeyed, $d(R_1,R_2) \le d(R_1,R_3) + d(R_2,R_3)$. If rectangle $R_i$ has corners $(x_i^1,y_i^1)$ and $(x_i^2,y_i^2)$, where $x_i^1 and $y_i^1, then the following would give you a metric for any $p\ge1$: $ d_p(R_1,R_2) = \left( \sum_{j=1}^2 |x_1^j-x_2^j|^p + |y_1^j-y_2^j|^p \right)^{1/p} $ The cases $p=1,2$ might be useful. Also, the limiting case $p\rightarrow \infty$ is a simple metric: $ d_\infty(R_1,R_2) = \max(|x_1^1-x_2^1|,|y_1^1-y_2^1|,|x_1^2-x_2^2|,|y_1^2-y_2^2|) $
In general you can can a metric from any norm on a 4-d space applied to the vector of differences in coordinates.
Also, if your concern is an algorithm for quickly finding neighbors, that's really a programming question, but look into quadtrees.