Existence of boolean function with exponential average case hardness
Let $C$ be a fixed function, and let $f$ be a random function. For $z \in \{0,1\}^n$, let $X_z = 1$ if $C(z) = f(z)$, and $X_z = -1$ otherwise. Thus
$$
2^{-n} \sum_z X_z = \Pr[C(z) = f(z)] - \Pr[C(z) \neq f(z)] = 2\Pr[C(z) = f(z)] - 1.
$$
Therefore $\Pr[C(z) = f(z)] \geq 1/2+\delta$ iff $2^{-n} \sum_z X_z \geq 2\delta$. According to Bernstein's inequality,
$$
\Pr\left[2^{-n} \sum_z X_z \geq 2\delta\right] \leq \exp \left(-\frac{42^n\delta^2}{2(1+2\delta/3)}\right) \leq e^{-2^n\delta^2}.
$$
(The true exponent is more like $-2^{n+1}\delta^2$.)
The number of (de Morgan) circuits of size $s$ is at most roughly $e^{2s\log s}$ (according to notes of Trevisan; the bound is not tight). According to the union bound, the probability (over $f$) that some circuit $C$ of size $s$ satisfies $\Pr[C(z) = f(z)] \geq 1/2+\delta$ is at most $e^{2s\log s} \cdot e^{-2^n\delta^2}$. If $2s\log s &lt; 2^n\delta^2$ then this probability is less than $1$, and so there exists some function $f$ such that $\Pr[C(z) = f(z)] &lt; 1/2+\delta$ for all circuits of size $s$.
You're interested in the setting $\delta = 1/s$. The argument works as long as $2s^3\log s &lt; 2^n$, and in particular, when $s\approx2^{n/3}$.