Without loss of generality you may assume that the horizontal spacing and vertical spacing are homogeneous.  If the side of length $a$ is split into $n_1$ parts and the side of length $b$ is split into $n_2$ parts, a direct application of the arithmetic mean vs geometric mean shows that the subrectangle diagonal is maximised if $n_1 = \sqrt{\frac{an}b}$ and $n_2 = \sqrt{\frac{bn}{a}}$.  Thus, you should try the two divisors of $n$ closest to the optimal value of $n_1$ and the one that gives you the smallest subrectangle diagonal is your optimal solution.

EDIT: You can try $n_1 = \left\lfloor \sqrt{\frac{an}b} \right\rfloor$ and $n_2 = \left\lfloor \sqrt{\frac{bn}{a}} \right\rfloor$ and then subdivide some of the small rectangles in order to have $n$.  This would give an approximation that is not terrible.