Okay, let's work backwards. Suppose we have $\alpha, \beta$ that minimizes $\max_i | y_i - \alpha x_i - \beta |$, and let us suppose that for this $\alpha, \beta$ the absolute error is maximized at $x_i = i$. We first point out that there must be some other $j \neq i$ such that $|y_j - \alpha x_j - \beta| = |y_i - \alpha x_i - \beta |$. Otherwise, we are free to change $\beta$ to reduce this error (and still have it be the max error). Furthermore, there must be a third index $k \neq i,j$ with the same absolute error, otherwise we could change $\alpha$ or $\beta$ to reduce both of the errors for $i,j$ simultaneously (change $\beta$ if both errors have the same sign, change $\alpha$ if the signs are different). Let $i. If we assume that no other indices have the same absolute error, then the signs of the errors must be either $+,-,+$ or $-,+,-$. If there are other indices with the same absolute error, then there must be some subsequence of error signs of that type.
Let us assume the $+,-,+$ sequence of error signs for now. Then we have
$ y_i - \alpha * i - \beta = \beta + \alpha * j - y_j = y_k - \alpha * k - \beta $
or
$ \alpha = \frac{y_k - y_i}{k-i} $ and $\beta = \frac{y_i + y_j}{2} - \frac{\alpha (i+j)}{2} = \frac{y_k + y_j}{2} - \frac{\alpha (k+j)}{2} = \frac{(j+k)y_i + (k-i)y_j - (i+j)y_k}{2(k-i)}$
and the maximum error is $F_{\min} \equiv \frac{(k-j)y_i + (i-k)y_j + (j-i)y_k}{2(k-i)}$.
Since this is the maximum error, we also have
$ \beta + \alpha * m - F_{\min} \leq y_m \leq \beta + \alpha *m + F_{\min}$ for all $m$.
The same formulas hold for the $-,+,-$ sign choice. This represents $(j,y_j)$ lying either above or below the line between $(i,y_i)$ and $(k,y_k)$ and all other points lying in the region defined by that line and the parallel line through $(j,y_j)$.
Now, the probability distribution for $F_{\min}$ is not too difficult to solve in an asymptotic limit: $U\rightarrow \infty, n/U \rightarrow 0$ drawing with or without replacement.
In either of these cases, we replace $y_i,y_j,y_k$ by $Y_i,Y_j,Y_k = y_i/U, y_j/U, y_k/U$. $F_{\min} = U f(Y_i,Y_j,Y_k)$ occurs with weight $(2 f(Y_i,Y_j,Y_k))^{n-3} * P(Y_i $ is the $i$th smallest draw and $Y_j $ is the $j$th smallest draw and $Y_k $ is the $k$th smallest draw$)$. We then divide by the sum/integral of all of the weights. The CDF of $P()$ is something like $(Y_i)^i (1-Y_k)^{n-k} (Y_j - Y_i)^{j-i} (Y_k - Y_j)^{k-j}$. Not a pretty integral. Furthermore, this ratio is going to give you the joint probability density of $(i,j,k,Y_i,Y_j,Y_k)$, not actually the probability density of $F_{\min}$. To get that, you would need to do another integration over that set of $(i,j,k,Y_i,Y_j,Y_k)$ that gives you a fixed value of $F_{\min}$.