Here is a quick argument showing that $P(\mathbf{md}(\pi)>m)\le Ce^{-cm}$ though I'll not try to make the bounds sharp. Let us consider $n$ independent random variables $X_k$ uniformly distributed on $[0,1]$. The rearrangement $\pi$ will be determined from that model as $\pi(k)=\#\{i\in[n]:X_i\le X_k\}$. Clearly, we have all orderings of $X$ equally likely, so this, indeed, generates the uniform distribution on $S_n$.
Now take $\delta>0$. The event that there exists no $k\in[n-1]$ with $|X_k-X_{k+1}|\le\delta$ has probability at most $e^{-\delta(n-1)}$ (just go left to right and use the fact that every time you exclude an interval of length at least $\delta$). Now consider the event that $|X_k-X_{k+1}|\le\delta$ but $|\pi(k)-\pi(k+1)|>m$. It means that some $m$ of other $n-2$ variables $X_i$ managed to squeeze into the interval between $X_k$ and $X_{k+1}$. Now it is easy to estimate the probability of this event for fixed $k$ by $2\delta$ (the probability that $X_k$ and $X_{k+1}$ are $\delta$-close) times ${n-2\choose m}\delta^m\le\frac{(n-2)^me^m}{m^m}\delta^m$ (the union bound over the choices of $m$ other variables that want to squeeze in between). Taking the union bound over $k$, we get
$$
P(\mathbf{md}(\pi)>m)\le e^{-(n-1)\delta}+(n-1)\delta \frac{(n-2)^me^m}{m^m}\delta^m.
$$
Choosing $\delta=\frac{m}{2e(n-1)}$ finishes the story.
You can, probably, play this trick in a much more intelligent way and get the true asymptotics, but I leave the bonus question to someone else :-)
