I think we can do better. I will describe different strategies where the probability that $d_i > d_j$ depends only on $i-j$. Then by choosing a weighted average, we will give a lower bound for this probability greater than $1/2$, despite the fact that the length of the sequence is around $n^2$.
 
First, if $k \leq mn-m+1$, then we take $d_i = \lceil \frac{i+e}{m} \rceil$ for a random $e \in [0,\dots, m-1]$. Then if $j>i$, the probability that $d_j>d_i$ is $\min ( \frac{j-i}{m},1)$.

To complement it, we want a sequence where the probability that $d_j>d_i$ is close to $1$ for $j-i$ small. We can do the first part by setting $d_i = i+e$ mod $n$ for again a random $n$. However, it declines to $0$ for $j-i$ large, so the best we can get by averaging is $1/2$.

We will do better using more randomization to change the rate of growth. Fix a natural number $l$ and let $\alpha$ be a random real number in $[0,l]$ and $\beta$ a random real number in $[0,n]$. Define $d_i = \lfloor \alpha i + \beta \rfloor$ mod $n$. Then fixing $\alpha$, the probability that $d_j < d_i$

$$f ( \alpha (j-i) \mod n)$$

where $f(x)= (1-1/n) x$ for $x \in [0,1]$ and $1- x/n$ for $x \in [1,n]$.

So the relevant probability is:

$$ \frac{1}{l} \int_0^l f ( \alpha (j-i) \mod n)) d \alpha$$

The probability  $\alpha(j-i)$ is in the interval $[0,1]$ modulo $n$, is clearly at most $1/l$.  So we may replace $f(x)$ with $1-x/n$ and only lose $1/r$. Another way of writing $1 - \frac{ x \mod n}{n}$ is $1- \operatorname{frac} \left( \frac{x}{n} \right)$

$$ \int_0^l \left( 1- \operatorname{frac}\left(\frac{\alpha (j-i)}{n} \right) \right) d \alpha$$

Using the trivial bound $ \operatorname{frac}(x) \leq x$, this is $\geq 1 - \frac{l}{2}(j-i)$.  

It is also easy to see that this is always at least $1/2$. This is because the average value of $1- \frac{x}$ on the whole interval $[0,1]$ is $1/2$, and the largest values come first, so averaging over any subinterval starting at $0$ produces a larger average.

So we have another strategy where the probability that $d_j-d_i$ is at least

$$\max( 1- \frac{l}{2} \frac{j-i}{n}, 1/2) - \frac{1}{l}$$.

Setting $m=n/r$, in our previous strategy the probability was at least:

$$\min( l \frac{j-i}{n}, 1) $$

Choosing a linear combination of $2/3$ this strategy and $1/3$ the previous, we get $2/3 - 2/3l$.


$k$ is proportional to $n^2/l$, hence to $n^2$. Letting $l$ got to $0$, the probability goes to $2/3$. So this shows that for $p=2/3-\epsilon$ we may take $ k \approx n^2$.

This shows that $n^{1/r}$ is not the right upper bound. Most likely this can be improved somewhat.