Existence of (Cut-Based) pseudorandom graphs beating the random graph The question is simply this: Does there exist a (family of) graph $G=(V,E)$ such that $\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}|\leq o(n^{3/2})$. Such graphs would be very pseudorandom as the edge density of all their cuts would be extremely close to the expected value if we had picked each edge with probability a half. 
Background: As discussed in the following Math-overflow question Max cut value in a random graph, with high probability a random $G(n,\frac{1}{2})$ graph has a cut $(S,S^c)$ with more than $\frac{n^2}{8}+\Omega(n^{3/2})$ edges. This implies that the following max-deviation lower bound:  For almost every $G=(V,E)$ we have,
$ \max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}| = \Omega(n^{3/2})$
This lower bound means that simply by taking a random graph you cannot solve the above problem. 
It could be true that the above for amost every graph result actually holds for every graph and this quantity is always $\Omega(n^{3/2})$. A proof of this would be quite interesting and would give evidence to a conjecture that I have in mind.
 A: This isn't a full solution, just a couple of observations too long to fit into a comment.  
First of all, it's worth noting that both of the "one-sided" versions of this statement are false.  In the complete bipartite graph $K_{n/2,n/2}$, every cut satisfies $E(S,S^C) \geq \frac{1}{2}|S||S^C|$, and in the union of two disjoint copies of $K_{n/2}$ every cut satisfies $E(S,S^C) \leq \frac{1}{2}|S||S^C|$ (these examples can be modified by adding $O(n)$ edges so that their density is exactly $1/2$ if $n$ is a multiple of $4$).  This rules out a number of arguments that attempt to construct (randomly or otherwise) an unusually dense cut.  
Secondly, the following weaker statement IS true: If $G$ is an $n/2$-regular graph, then there are disjoint subsets $S$ and $T$ such that $E(S,T) \geq \frac{1}{2}|S| |T| + \Omega(n^{3/2})$.  A rough sketch of the argument is to take $S$ to be a random subset of the vertices where each vertex is in $S$ with probability $0.1$, then take $T$ to be all the vertices outside of $S$ having at least $|S|/2+0.01 \sqrt{n}$ neighbors in $S$.  This automatically forces $E(S,T) \geq |S||T|/2+0.01 |T| \sqrt{n}$, so we just need to show that $|T|$ is large for some $S$.  
Each vertex is in $T$ with positive probability (this is where we need regularity), so the expected number of vertices in $T$ is at least $cn$.  This means that some $S$ must have a $T$ at least this large.  
Unfortunately, this probably does not extend to an argument giving a cut across the whole graph, since the conclusion is one-sided.  
