This answer addresses your update "Any bound of $Z$ is helpful." It does not give the probability distribution of $Z$.
For fixed $m$ and $n$ with $n < m$, we have $Z \leq n \left(\frac{m+1}{n+1}-1\right),$ and for fixed $m$, where $n$ is allowed to range over all possible values from $1$ to $m$, we have $Z \leq \left(\sqrt{m+1}-1\right)^2.$
For the first inequality, let
$m$ and
$n$ be fixed with
$n < m$. So
$\frac{m+1}{n+1} > 1$. Thus the maximum possible value of
$\left|X_i - \frac{(m+1)i}{n+1}\right|$ occurs for one of the extreme values in an extreme
in the other direction sample. In other words, the largest possible value of
$Z$ occurs with
$Y_n$ when the sample
$\{1, 2, \ldots, n\}$ is chosen or with
$Y_1$ when the sample
$\{m-n+1, m-n+2, \ldots, m\}$ is chosen. By symmetry, these two values should be equal, and that is the case: In the first sample, we have
$Y_n = \left|n - \frac{(m+1)n}{n+1}\right| = n \left(\frac{m+1}{n+1}-1\right)$, and in the second sample we have
$Y_1 = \left|m-n+1 - \frac{m+1}{n+1}\right| = (m+1)\left(1 - \frac{1}{n+1}\right) - n = n \left(\frac{m+1}{n+1}-1\right).$ Thus
$Z \leq n \left(\frac{m+1}{n+1}-1\right).$ To see the second inequality, just use calculus to maximize the expression $f(n) = n\left(\frac{m+1}{n+1}-1\right)$. We get that $f(n)$ is maximized when $n = \sqrt{m+1}-1$, and thus $Z \leq \left(\sqrt{m+1}-1\right)^2$.
As an illustration of this last result, consider the numerical work posted by Sasha. The largest values of $Z$ occur on the plots for which $n$ is closest to $\sqrt{m+1}-1$.