I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$.
So far I have been able to prove that the number of gates required lies between $\Omega(2^n/n)$ and $O(2^n)$, but I need a better upper bound.
The actual one was proved as follows. We observe that
$f(x_1,\dots, x_n) = (\neg x_n \wedge f(x_1,...,x_{n-1},0))\lor(x_n \wedge f(x_1,...,x_{n-1},1))$ $(1)$
so it must be that the number of circuits required to compute the hardest function on n bits, $\lambda (n)$, is less than $5 + 2\lambda (n-1)$. A quick check shows than then $\lambda(n) = O(2^n)$.
I tried a similar analysis to prove the stronger bound. My strategy was to apply the expansion $(1)$ only for $n-log(n)$ levels. That allows us to determine that $\lambda(n) = O(2^{n-log(n)} + X)$, where $X$ is the number of gates required to compute the remaining $2^{n-k}$ functions on $log(n)$ bits.
If I somehow showed that $X = O(2^n/n)$ then I would have the result. But I cannot think of a way to do so.
So it turns out that the question was actually easy to answer.
Consider a minimal circuit of $2^{n}/n$ gates with $log(n)$ inputs; that is, no two nodes of the circuit compute the same function. This is certainly doable, since we are not limited by fan-out. Then it stands to reason that every function on $log(n)$ bits is computed by some node, which we can use to get the answer we need.
Thus $X = 2^{n}/n$, and the result follows as I reasoned in the question.