Constructions better than a random one. I am interested in examples of constructions in the complexity theory which are better than a random constructions. 

The only one example of such construction which I know is in the field of error-correcting codes. Algebraic-geometry codes are better in some range of parameters than a random codes.

One can easily to construct such artificial examples. 
I am interested in the examples like algebraic geometry codes, where it is easy make a random construction and it is not obvious how to do better.
Ramanujan graphs have second eigenvalue $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ (with $D$ the degree of the graph), while random graphs only achieve $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ w.h.p. In fact, in general we have that $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$, with the $o(1)$ term going to $0$ with $D$ held constant (as the number of vertices $N\rightarrow \infty$), so in some sense these are optimal.