Let's consider an easier version of the problem, suppose you only need to find one point that has the minimum Manhattan distance to all ~N~ points.

Let this point be ~(x,y)~, then the distance to all ~N~ points can be written as this: ~\sum_{i=1}^N|x-x_i|+|y-y_i|=\sum_{i=1}^N|x-x_i|+\sum_{i=1}^N|y-y_i|~. As the ~x~ and ~y~ coordinate are independent, we minimize each summand seperately.

Finding the the value of ~x~ that minimizes ~\sum_{i=1}^N|x-x_i|~ is a classic problem, which you can solve by calculating the median of the array ~x_1,x_2,\dots,x_N~. In fact, moving away from ~x~ will never decrease the total sum.

Now back to the original problem, we need to find two points that minimize the distances. It's clear that the point we found above must be one of them. In fact the second point is just near the first point. Let the second point be ~(x',y')~, then I claim ~|x-x'|+|y-y'|=1~, that is, it's one of the four neighbours of the first point.

Still, we consider each dimension seperately, find ~x,x'~ that minimize ~\sum_{i=1}^N|x-x_i|+\sum_{i=1}^N|x'-x_i|~. Suppose ~x~ is the median, as moving away from it will always increase the answer, therefore, the optimal choice of ~x'~ would be one of ~x\pm 1~. Therefore in the two dimensional case, we must have ~x'=x\pm1,y'=y\pm1~.

You could check all ~8~ integer points around ~(x,y)~, but it suffices to check only the four neighbours.