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.