I adapt an argument from [this blog post of mine][1], exploiting the $\ell^2$ boundedness of the discrete Hilbert transform (i.e. [Hilbert's inequality][2]), 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][3] (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))}$.

  [1]: https://terrytao.wordpress.com/2013/10/29/a-spectral-theory-proof-of-the-algebraic-regularity-lemma/
  [2]: http://en.wikipedia.org/wiki/Hilbert%27s_inequality
  [3]: http://arxiv.org/abs/0909.2190