Number of circuits with at most $m$ logic gates
I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly.

You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves $16(m+n)^2$ possibilities for the type of each gate. Since there are $m$ gates, at first glance there should be $(16(m+n)^2)^m$ different circuits we could construct from these gates. 

However, we should also specifically select for the output gate, so we multiply the number of circuits by $m$ to account for this choice: thus we have a bound of $m\cdot(16(m+n)^2)^m$ different possible circuits of size $m$.

The crucial step that you are missing is that the labels we assigned to each of our gates were arbitrary, and thus we can divide our bound by $m!$ to compensate for our overcounting.

We thus have a tighter bound of
$$\frac{m \cdot (16 (m+n)^2)^m}{m!}$$ for the number of circuits of size $m$. 

If we assume $m = (1-\epsilon)\frac{2^n}{n}$, for any $\epsilon&gt;0$, one can (and Katz does) show that this is less than $2^{2^n}$.