Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ y_i $ is the output of $ f_i $ and satisfying $ Size(C_n)\in O(2^{2^n}) $
Remark: The circuit is in a model of fan-in 2.
I've already found a solution in $ O(2^{2^n + n}) $ but I can't find less even recursively.
Given the circuit $C_n$, you can compute $C_{n+1}$ using $O(2^{2^{n+1}})$ additional gates. Indeed, each output gate of $C_{n+1}$ is of the form $$ (\lnot x_{n+1} \land y_i) \lor (x_{n+1} \land y_j) $$ for some $i,j$, so can be computed from the outputs of $C_n$ using $O(1)$ additional gates.
In total, the circuit $C_n$ uses $O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$ gates.
There is such a circuit with exactly $2^{2^n}$ nodes (which is, of course, minimal possible). I’m assuming arbitrary nodes in the circuit can be designated as output nodes, including input nodes and nodes of nonzero fan-out; otherwise you would have to copy them, leading to at most double the size.
Start with the $n$ input nodes $x_1,\dots,x_n$, and repeat the following in arbitrary order until it is no longer applicable, where $f_y$ denotes the Boolean function computed by node $y$ of the circuit:
Pick a node $y$ such that $\neg f_y$ is not computed by any node of the circuit, and add a new node $\neg y$.
Pick a pair of nodes $y$ and $y'$ such that $f_y\land f_{y'}$ is not computed by any node of the circuit, and add a new node $y\land y'$.
When the construction stops, the set of functions $\{f_y:y\in C\}$ is closed under $\neg$ and $\land$, hence it contains all Boolean functions in $n$ inputs. On the other, by construction, no two nodes of the circuit compute the same function. Thus, the size of the circuit equals the number of functions in $n$ variables, viz. $2^{2^n}$.
An alternative construction with the same result: take any circuit that computes all functions in $n$ inputs, and keep removing redundant nodes. That is, if $y\ne y'$ compute the same function, and (wlog) $y$ does not depend on $y'$, then remove $y'$, and redirect all output wires of $y'$ to use $y$ instead. When you cannot do this any longer, no two nodes compute the same function, hence the size of the circuit is $2^{2^n}$, again.
