In order to get to the minimum distance problem quickly, we quote a formula for the distance from the point $(x_0,y_0)$ to the line with equation $px+qy+r=0$. This distance is
$$\frac{|px_0+qy_0+r|}{\sqrt{p^2+q^2}}.$$
The site linked to gives a proof, as does Wikipedia. The distance from a point to a line has also been discussed more than once on StackExchange.
For our minimization problem, we can assume that one of the points is $(0,0)$, and the other is, say, $(a,b)$. So the line has equation $bx-ay=0$. We can assume that $a$ and $b$ are relatively prime, for if $d$ is their greatest common divisor, the same line is determined by $(0,0)$ and $(a/d,b/d)$.
Then by Bezout's Theorem, we can find integers $x_0$, $y_0$ between $0$ and $\max(a,b)$ such that $|bx_0-ay_0|=1$. Thus the smallest non-zero value of $|bx-ay|$ as $(x,y)$ ranges over our grid is $1$.
So the minimum possible non-zero distance from a gridpoint to our line is $\dfrac{1}{\sqrt{a^2+b^2}}$.
Now we want to maximize $a^2+b^2$, as $(a,b)$ ranges over relatively prime pairs on our grid. Then for fixed $a+b$, this maximum occurs when $a$ and $b$ differ by as little as possible. If $n=1$, the maximum value of $\sqrt{a^2+b^2}$ is achieved when $a=b=1$.
Suppose now that $n>1$. Then
the maximum value of $a^2+b^2$, given that $\gcd(a,b)=1$ and $(a,b)$ is on our grid is attained at $a=n-1$, $b=n$, and at $a=n$, $b=n-1$. The minimum non-zero distance is therefore
$$\frac{1}{\sqrt{2n^2-2n+1}}.$$
Comment: For our particular problem, we do not need Bezout's Theorem, since if $n>1$ then the distance from $(1,1)$ to the line through $(0,0)$ and $(n-1,n)$ is $1/(2n^2-2n+1)$. It is clear that we can't do better, since $|bx_0-ay_0|$ is at least $1$. However, if the $n\times n$ grid is replaced by an $m\times n$ grid, the natural analysis uses Bezout's Theorem.
