1) The perfect separation dimension of $K_n$ is linear in $n$, up to a small polylogarithmic factor. In fact, it is at least $n/2-1$ and at most $n(\log n)^{1+o(1)}$.
2) For almost all graphs, the separation dimension is also linear in $n$, up to a logarithmic factor. This follows as a special case of a more general result showing that the perfect separation dimension of the random graph $G(n,p)$ is w.h.p. $\Omega(np/\log n)$ for a wide range of values of $p$, including all constant $p$.
3) Significantly relaxing perfection to just requiring that any pair of disjoint edges is separated the same number of times up to a difference of $c\log n$ for some absolute constant $c$, still requires the dimension for $K_n$ to be $\Omega(n)$. This is perhaps surprising as it is known that if we allow a difference of $7\log n$, then the dimension reduces to only $\Theta(\log n)$.