The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $\Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $\Theta(n \log n)$ in the worst-case, and so achieve the $\Omega(n \log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $\log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $\log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $\log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in $\{a_1,a_2,a_3\}$ are smaller than or larger than the elements in $\{a_4,a_5\}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.