Average codeword length in a Huffman tree is $\Omega(\log n)$
This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $n$.

Let us show that any prefix code satisfies your property. Consider any prefix code whose codewords have lengths $\ell_1,\ldots,\ell_n$. Kraft's inequality shows that
$$
2^{-\ell_1} + \cdots + 2^{-\ell_n} \leq 1.
$$
The function $x \mapsto 2^{-x}$ is convex, hence
$$
\frac{1}{n} \geq \frac{2^{-\ell_1} + \cdots + 2^{-\ell_n}}{n} \geq 2^{-(\ell_1+\cdots+\ell_n)/n}.
$$
It follows that
$$
\frac{\ell_1 + \cdots + \ell_n}{n} \geq \log_2 n.
$$
Since $x \mapsto 2^{-x}$ is strictly convex, there can be equality only if $\ell_1 = \cdots = \ell_n$, that is, only if all codewords are of length exactly $\log_2 n$. That can only happen if $n$ is a power of 2. This leaves open the following question:


  What is the minimum average codeword length of a prefix code on $n$ symbols?


(We note in passing that every prefix code satisfying Kraft's inequality tightly is a minimum redundancy code for some distribution, namely the one in which the probability of the $i$th symbol is $2^{-\ell_i}$.)

To answer this, let us note that convexity implies that if $a &lt; b$ then
$$
2^{-a} + 2^{-b} \geq 2^{-(a+1)} + 2^{-(b-1)}.
$$
(We can also see this directly: without loss of generality $a=0$, and then we need to prove $1 + 2^{-b} \geq 1/2 + 2 \cdot 2^{-b}$, that is, $1/2 \geq 2^{-b}$, which follows from $b \geq 1$.)

Applying this operation repeatedly starting at some arbitrary integer solution of Kraft's equation, we eventually reach a solution which involves at most two different values $\ell,\ell+1$. If $n = 2^k + m$, where $0 \leq m &lt; 2^k$, then this solution must consist of $2^k - m$ many $k$'s and $2m$ many $k+1$'s. Hence the optimal average codeword length is
$$
\frac{k(2^k-m)+(k+1)2m}{2^k+m} = k + \frac{2m}{2^k+m}.
$$