If, as suggested by Ori Gurel-Gurevich, we sample from uniform distribution on $[0,1]$, then $Z$ will typically be of order $1/\sqrt{n}$.

A convenient way of generating the points $X_1,\dots,X_n$ in order is letting $W_1,\dots,W_{n+1}$ be independent exponential(1) variables with partial sums $S_k = W_1+\cdots+W_k$, and finally letting $X_k = S_k / S_{n+1}$. We have $$\left|X_k - \frac{k}{n+1}\right| \leq \frac{\left|S_k-k\right| + \left|S_{n+1} - (n+1)\right|}{n+1},$$ and in particular $$\max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| \leq \frac2{n+1}\cdot\max_{k\leq n+1} \left|S_k - k\right|.$$ It is relatively easy to see that $\mathbb{E}\max_{k\leq n} \left|S_k-k\right| = O(\sqrt{n})$ and consequently that $\mathbb{E} \max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| = O(n^{-1/2})$. This is because $S_n-S_k$ is independent of $S_k$. Therefore if $S_k$ deviates wildly from its mean, then with decent probability (namely when $S_n-S_k$ deviates ever so slightly in the same direction), $S_n$ will deviate just as wildly from its mean. More precisely, $$Pr\left(\left|S_n - n\right| > t\right) \geq C\cdot Pr\left(\left|S_k-k\right| > t \ \text{for some $k\leq n$}\right),$$ where $C$ is simply a positive lower bound on the probability that a sum of independent exponentials deviates from its mean in a given direction. Consequently \begin{equation} \mathbb{E} \max_{k\leq n} \left|S_k-k\right| = \int_0^\infty Pr\left(\max_{k\leq n}\left|S_k-k\right| > t\right) \, dt \end{equation} \begin{equation} \leq \frac1C \int_0^\infty Pr\left(\left|S_n-n\right| > t\right)\, dt = \frac1C\cdot \mathbb{E}\left|S_n-n\right| = O(\sqrt{n}). \end{equation}

If, as suggested by Ori Gurel-Gurevich, we sample from uniform distribution on $[0,1]$, then $Z$ will typically be of order $1/\sqrt{n}$.

A convenient way of generating the points $X_1,\dots,X_n$ in order is letting $W_1,\dots,W_{n+1}$ be independent exponential(1) variables with partial sums $S_k = W_1+\cdots+W_k$, and finally letting $X_k = S_k / S_{n+1}$. We have $$ \left|X_k - \frac{k}{n+1}\right| = \left|\frac{S_k}{S_{n+1}} - \frac{k}{n+1}\right| \leq \left|\frac{S_k}{n+1} - \frac{k}{n+1}\right| + \left|\frac{S_k}{n+1} - \frac{S_k}{S_{n+1}}\right| $$ $$ \leq \frac{\left|S_k-k\right|}{n+1} + \frac{S_{n+1}}{S_k}\cdot \left| \frac{S_k}{n+1} - \frac{S_k}{S_{n+1}}\right| = \frac{\left|S_k-k\right| + \left|S_{n+1} - (n+1)\right|}{n+1},$$ and in particular $$\max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| \leq \frac2{n+1}\cdot\max_{k\leq n+1} \left|S_k - k\right|.$$ It is relatively easy to see that $\mathbb{E}\max_{k\leq n} \left|S_k-k\right| = O(\sqrt{n})$ and consequently that $\mathbb{E} \max_{k\leq n} \left|X_k - \mathbb{E}X_k\right| = O(n^{-1/2})$. This is because $S_n-S_k$ is independent of $S_k$. Therefore if $S_k$ deviates wildly from its mean, then with decent probability (namely when $S_n-S_k$ deviates ever so slightly in the same direction), $S_n$ will deviate just as wildly from its mean. More precisely, $$Pr\left(\left|S_n - n\right| > t\right) \geq C\cdot Pr\left(\left|S_k-k\right| > t \ \text{for some $k\leq n$}\right),$$ where $C$ is simply a positive lower bound on the probability that a sum of independent exponentials deviates from its mean in a given direction. Consequently \begin{equation} \mathbb{E} \max_{k\leq n} \left|S_k-k\right| = \int_0^\infty Pr\left(\max_{k\leq n}\left|S_k-k\right| > t\right) \, dt \end{equation} \begin{equation} \leq \frac1C \int_0^\infty Pr\left(\left|S_n-n\right| > t\right)\, dt = \frac1C\cdot \mathbb{E}\left|S_n-n\right| = O(\sqrt{n}). \end{equation}

EDIT: To return to the original problem, we choose $n$ numbers independently and uniformly in the interval $[0,m-n+1]$ and let $$U_1\leq U_2 \leq \cdots \leq U_n$$ be the sorted sequence. Now let $$X_i = \left\lfloor U_i+i\right\rfloor.$$ The sequence $X_1,\dots,X_n$ is now generated according to the question (and therefore not the same as the $X_i$'s earlier in this post).

Scaling up the result above by a factor $m-n+1$, we see that the maximum deviation of a $U_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}\right),$$ while the difference between $X_i$ and $U_i$ is of order $n$. Therefore the maximum deviation of $X_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}+n\right),$$ where the first term will dominate when $m>>n^{3/2}$. On the other hand if $m$ is smaller, say of the same order as $n$, it must clearly be possible to achieve sharper bounds.