I adapt an argument from this blog post of mine, exploiting the $\ell^2$ boundedness of the discrete Hilbert transform (i.e. Hilbert's inequality), to obtain an exponential upper bound. I don't see any obvious way to improve this to a polynomial bound (EDIT: A Whitney decomposition seems to do the trick, see below). The argument is inspired by a stability result of Hrushovski (based on de Finetti's theorem) which shows that some finite bound is possible, although it is not easy to extract a quantitative bound from Hrushovski's argument (and if one did, it would surely be worse than exponential); see Proposition 2.25 of that paper.
Suppose that ${\bf P}(d_j > d_i) \geq r$ for some $r>1/2$ and all $1 \le i < j \leq k$. Then of course $${\bf P}( d_j > d_i) - {\bf P}( d_j < d_i ) \geq 2r-1$$ for all $1 \le i < j \le k$. We expand this as $$ \sum_{1 \leq a < b \leq n} {\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b ) \geq 2r-1.$$ Multiply by the positive quantity $\frac{1}{j-i}$ and sum to conclude that $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i < j \leq k} \frac{1}{j-i} [{\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b )] \gg (2r-1) k \log k \qquad (1).$$ The LHS can be rearranged as $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} {\bf P}(d_j = b \wedge d_i = a ) $$ and rearranged further as $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a}.$$ By Hilbert's inequality, we have $$ \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll (\sum_{1 \leq j \leq k} 1_{d_j=b})^{1/2} (\sum_{1 \leq i \leq k} 1_{d_i=a})^{1/2}$$ and $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq j \leq k} 1_{d_j=b}, {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i \leq k} 1_{d_i=a} \ll k n $$ so by Cauchy-Schwarz $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll kn $$ and hence $$ kn \gg (2r-1) k \log k$$ leading to the exponential upper bound $$ k \ll \exp( O( \frac{n}{2r-1} ) ).$$
EDIT: Looks like one can improve this to the polynomial bound $k \ll n^{O(1/(2r-1))}$ using the following standard Whitney decomposition trick (used for instance to prove the Rademacher-Menshov theorem or the Christ-Kiselev lemma). Firstly, without loss of generality we may take $n$ to be a power of 2. Then observe that if $1 \leq a < b \leq n$, then there is a unique pair of distinct dyadic intervals $I,J$ in $\{1,\dots,n\}$ with the same parent such that $a \in I$ and $b \in J$; let's call such pairs "adjacent". As such, the LHS of (1) can now be rearranged as
$$ {\bf E}\sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_J(d_j) 1_I(d_i).$$
We apply Hilbert's inequality to bound this by $$ \pi {\bf E} \sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} (\sum_j 1_J(d_j))^{1/2} (\sum_i 1_I(d_i))^{1/2}$$ which by Cauchy-Schwarz and the disjointness of the $I,J$ can be bounded by $$ \pi \sum_{2^l < n} k^{1/2} k^{1/2} \ll k \log n$$ leading to $$ k \log n \gg (2r-1) k \log k $$ and thus $k \ll n^{O(1/(2r-1))}$.