Answer: $\left(\frac{1}{2}+o(1)\right) \frac{n}{m} + \delta$, where $|\delta| < 1$ and $o(1)$ tends to $0$ as $m\to \infty$.
First of all, note that since all $a_i$ are independently and identically distributed, $\mathbb{E}[x| j =1] = \mathbb{E}[x| j = 2] = \dots = \mathbb{E}[x| j =m],$ so it doesn't matter whether we choose $j$ randomly or just let $j=1$. Let's assume that $j=1$.
It's easier to work with continuous random variables. So let's assume that we choose independent random numbers $y_1, \dots, y_m \in_U (0,1)$ and then let $x_i = \lceil ny_i\rceil$. Note that $n|y_i - y_j| - 1 < |x_i - x_j| < n|y_i - y_j| + 1.$ Therefore, if we are only interested in an approximate answer, it suffices to find the expectation $\mathbb{E}[|y_i - y_j|]$. We reduced our problem to the following problem.
We are given $m$ independent random variables $y_1, \dots, y_m$ uniformly distributed on $(0,1)$. Compute the expectation of $\xi = \min_{i>1} |y_1-y_i|$.
Here is an informal solution to this problem. \begin{align*}\mathbb{E}[\xi] &= \int_0^1 \Pr[\xi > t] dt = \int_0^1 \Pr[|y_1 - y_i| > t \text{ for every } i > 2]\, dt \\ &= \int_0^1 \mathbb{E}[\Pr[|y_1 - y_2| > t]^{m-1}|y_1] \,dt. \end{align*} Since there are $m$ numbers $\{y_i\}$ on $(0,1)$, we expect that the distance between consecutive numbers will be about $1/m$; it's very unlikely that the distance is more than $\tau = \log m /m$. Thus $\xi < \tau$ with very high probability, also $y_1 \in(\tau, 1 - \tau)$ w.h.p. Let us condition on $y_1 = y^*$ where $y^* \in (\tau, 1 - \tau)$. Then we have \begin{align*} \int_0^1 \Pr[|y_1 - y_2| > t | y_1 = y^*]^{m-1} dt &\approx \int_0^{\tau} \Pr[|y_2 - y^*| > t]^{m-1} dt \\ &= \int_0^{\tau} \Pr[y_2\notin [y^* -t, y^*+t]]^{m-1} dt\\ &=\int_0^{\tau} (1 - 2t)^{m-1} dt. \end{align*} Since $y_1 \in(\tau, 1 - \tau)$ w.h.p, we have $\mathbb{E}[\xi] \approx \int_0^{\tau} (1 - 2t)^{m-1} dt \approx \frac{1}{2m}. $
Finally, $\mathbb{E}[\xi] \in (n\mathbb{E}[\xi] - 1, n\mathbb{E}[\xi] +1)$. Plugging in the expression for $\mathbb{E}[\xi]$, we get $\mathbb{E}[\xi] \in \left(\left(\frac{1}{2}+o(1)\right) \frac{n}{m} -1 , \left(\frac{1}{2}+o(1)\right) \frac{n}{m} +1\right).$
Note that this bound is not particularly useful when $m\approx n$.