How good is the Huffman code when there are no large probability letters?
There are lots of papers that study exactly the problem you mention. The first in the series is a paper by Gallager, "Variations on a Theme by Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. He proves that the difference between the average codeword length of an Huffman code and the entropy  (he calls that quantity "redundancy") is always strictly less than $p$ (= largest probability in the probability distribution), in the case  $p\geq 1/2$, and it is less than $p+0.086$, if $p&lt;1/2$. Better bounds are known, you can find them in the numerous papers that quote Gallager work.