Let $X$ be a natural number chosen uniformly at random from $1, . . . , n$. I'd like to see how the bounds of $P(X \geq \frac{(n+1)}{2} + r\sqrt{n})$ behave as $n \to \infty$ for some value of $r > 0$. First, I need to obtain the bounds using Markov's and Chebyshev's inequality.
This is how I did it: If $X$ is a natural number chosen uniformly at random from $1, . . . , n$, then $P(X = 1) = \frac{1}{n}, P(X = 2) = \frac{1}{n}, \dotsc, P(X = n) = \frac{1}{n}$. So,
$$E(X) = \sum_{j=1}^n\frac{j}{n} = \frac{1}{n}\frac{n(n-1)}{2} = \frac{n-1}{2}$$ and $$E(X^2) = \sum_{j=1}^n\frac{j^2}{n} = \frac{1}{6}(2n^2+3n+1).$$ Therefore,
\begin{align} \text{Var}(X) &= E(X^2) - E(X)^2 \\ &= \frac{1}{6}(2n^2+3n+1) - \frac{(n-1)^2}{4}\\ &= \frac{(n+1)(2n + 1)}{6} - \frac{(n-1)^2}{4}\\ &= \frac{2(n+1)(2n + 1) - 3(n-1)^2}{12}\\ &= \frac{n^2+12n-1}{12} \end{align} Now, $$P(X \geq \frac{(n+1)}{2} + r\sqrt{n}) = P(X - \frac{(n-1)}{2} \geq 1 + r\sqrt{n})$$ since $\frac{(n+1)}{2} = \frac{(n-1+1+1)}{2} = \frac{(n-1)}{2} + 1$. Because $1 + r\sqrt{n}$, I can use Chebyshev's inequality in the following manner \begin{align} P(X - \frac{(n-1)}{2} \geq 1 + r\sqrt{n}) &= P(|X - \frac{(n-1)}{2}| \geq 1 + r\sqrt{n})\\ &\leq \frac{\text{Var(X)}}{(1+r\sqrt{n})^2}\\ &= \frac{n^2+12n-1}{12(1+r\sqrt{n})^2}, \end{align} which is the bounds for $P(X \geq \frac{(n+1)}{2} + r\sqrt{n})$. But when I plot the bounds, all I can conclude is that the bound goes to infinity (when $n \to \infty$) for small $r$. For large $r$, it seems that the bound goes to $0$ (also when $n \to \infty$). Am I doing the calculation correctly?
There is one error in your calculations but it isn't an important one. It is in the equality \begin{equation} P(X - \frac{(n-1)}{2} \geq 1 + r\sqrt{n}) = P(|X - \frac{(n-1)}{2}| \geq 1 + r\sqrt{n}) \end{equation} Consider $n = 25$ and $r = 1$ so that $$P(X - \frac{(n-1)}{2} \geq 1 + r\sqrt{n}) = P(X - 12 \geq 6) = P(X \geq 18) = 8/25$$ while $$P(|X - \frac{(n-1)}{2}| \geq 1 + r\sqrt{n}) = P(|X - 12| \geq 6) = P(X \in \{1,2,...,6\}\cup\{18,19,...,25\}) = 14/25$$ In general the second bound should be just a bit less than double the first. However, this doesn't change the fact that the limit in the bound from Chebyshev goes to $+\infty$, this is because Chebyshev is often quite a loose bound when applied near the expected value. Let me make this precise.
One way of stating Chebyshev's inequality is that \begin{equation} P(|X - EX| > k) \leq \frac{Var(X)}{k^2} \end{equation} When $k << \sqrt{Var(X)}$ then \begin{equation} 1 <<\frac{Var(X)}{k^2} \end{equation} and we see that Chebyshev becomes a very bad bound. Now let's look at $k$ and $Var(X)$ when $n$ becomes very large.
\begin{align} k &= 1 + r\sqrt{n} \approx r\sqrt{n} \\ \sqrt{Var(X)} &= \sqrt{(n^2 + 12n - 1)/12} \approx \frac{n}{12} \end{align} (remember I'm using $n$ big enough that everything else doesn't contribute much). From this we see that for large $n$ (unless $r$ is also very large) \begin{equation} k \approx r\sqrt{n} << \frac{n}{12} \approx \sqrt{Var(X)} \end{equation} and we see that the bound from Chebyshev really should be quite a bad bound when $n$ is big (unless as you pointed out $r$ is also big).