The reason that creation and destruction operators don't commute is that, on top of 'moving a state up and down energy levels', they multiply it by a number in the process, and this number depends on where you are in the ladder. More specifically,
$$\begin{cases}
\hat{a}|n\rangle&=\sqrt{n}|n-1\rangle,\text{ while}\\
\hat{a}^\dagger|n\rangle&=\sqrt{n+1}|n+1\rangle.
\end{cases}$$

Thus, if you act on a number state $|m\rangle$ with a creation operator first, you will get the $\sqrt{n+1}$ factor with $m=n$, but the $\sqrt n$ factor with $n=m+1$, so you will get $\hat a \hat a^\dagger|m\rangle=(m+1)|m\rangle$. Conversely, if you act with the destruction operator first, you will get a factor with $\sqrt n$ at $n=m$, and then a factor of $\sqrt{n+1}$ at $n=m-1$, so the result will be $\hat a^\dagger \hat a|m\rangle=m|m\rangle$.

Ultimately, though, there is a more fundamental reason why creation and annihilation operators can't commute, and it is the fact that *energy levels are bounded from below:* that is, there are no $|n\rangle$ with $n<0$. To see why this is the case, consider the creation and annihilation operators without the prefactors I just talked about, to get
$$\begin{cases}
\hat{E}\,|n\rangle&=|n-1\rangle\text{ and}\\
\hat{E}^\dagger|n\rangle&=|n+1\rangle.
\end{cases}$$

The argument above no longer holds, and both routes will return the same coefficient on $|m\rangle$ after applying $\hat E$ and $\hat E^\dagger$ in both orders. The problem, however, is *what happens to the ground state?* The formulas above are mostly fine, but they do not specify what $\hat E|0\rangle$ should be, and there is no $|-1\rangle$ state we can put it into. However, if we want both operators to be hermitian conjugates, then we have really no room to play with, because the identity
$$
\langle n|\hat E|0\rangle^\ast=\langle 0|\hat E^\dagger|n\rangle=\langle 0|n+1\rangle=0
$$
implies that $\hat E|0\rangle$ has zero component along $|n\rangle$ for all $n\geq0$; since that is a complete set, it implies that $\hat E|0\rangle=0$.

Finally, then, if you compute $\hat E\hat E^\dagger |0\rangle$ as above, you will get $|1\rangle$ as normal, but $\hat E^\dagger \hat E|0\rangle$ returns 0, which is different, and the operators don't commute:
$$\hat E\hat E^\dagger =1\text{ but }\hat E^\dagger \hat E=1-|0\rangle\langle 0|.$$

The only way around this is to allow for an infinite ladder of negative-energy eigenstates, which are completely unphysical, but *do* allow for commuting ladder operators. While these states have indeed appeared in the literature they are unwieldy to use as they defy all intuition and they have not caught on.

So, to answer your final question: the asymmetry in the harmonic oscillator that ultimately causes this behaviour is the fact that the ladder of energy eigenstates is bounded from below but not from above, which makes going up and down the ladder not completely equivalent.

Assumptions: I will be talking about Hermitian (more generally self-adjoint) operators only. This means that I will assume that the operators in question have a set of eigenvectors that span the Hilbert space. As mentioned by `tomasz`

in a comment, this is not exactly necessary, since more general statements can be made, but since we are dealing with basic QM, I figure this simplification is reasonable.

**Questions 1 and 2**

The statement is that if two operators commute, then *there exists* a basis for the space that is simultaneously an eigenbasis for both operators. However, if (for instance) one of the operators has two eigenvectors with the same eigenvalue, any linear combination of those two eigenvectors is also an eigenvector of that operator, but that linear combination might *not* be an eigenvector of the second operator.

Case in point: we consider the states $|l,m\rangle = |1,1\rangle$ and $|l,m\rangle = |1,-1\rangle$. These are both eigenvectors of $\hat{L}^2$ and $\hat{L}_z$. The eigenvalues of $\hat{L}_z$ are $\hbar$ and $-\hbar$, respectively, but the state
$$|1,1\rangle + |1,-1\rangle$$
is clearly *not* an eigenvector of $\hat{L}_z$, but it *is* still an eigenvector of $\hat{L}^2$. This is *probably* why we use the term "mutual" rather than "same". Finally, we form linear combinations of the $|1,m\rangle$ states to get the $l=1$ states that are eigenvectors of, say, $\hat{L}_y$.

As a straight-forward example, consider the following two matrices:
$$L = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1
\end{array}}
\right]$$
and
$$Z = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1
\end{array}}
\right].$$
The vectors $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$ are eigenvectors of both operators. The latter two are eigenvectors of $L$ with the *same* eigenvalue (namely $1$), but they are eigenvectors of $Z$ with *different* eigenvalues (namely, $1$ and $-1$). If we instead use the vectors $(0,1,1)$ and $(0,1,-1)$, these are still eigenvectors of $L$ with eigenvalue $1$, but they are no longer eigenvectors of $Z$, as you can verify.

**Question 3**

As cleverly pointed out by `Chris White`

in a comment, the identity operator commutes with *every single other operator*, and yet there are operators that don't commute with each other. This is the simplest of counter-examples to your intuition. Commutativity is not a transitive property.

I don't know whether your intuition about the problem was mathematical or physical. If it was physical, then this is something you have to just get used to, because it is part of nature that things work this way. If it is mathematical, then perhaps the counter-example provided above will help.

As a straight-forward example, add to the above matrices the matrix
$$X = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0
\end{array}}
\right]$$
This operator commutes with $L$ but not $Z$.

**Question 4**

It is certainly okay for two operators that don't commute to share an eigenvector. In fact, $\hat{L}_x$, $\hat{L}_y$, and $\hat{L}_z$ all share an eigenvector: the state $|l,m\rangle = |0, 0\rangle$.

As a more trivial example of operators that share an eigenvector that don't commute, consider the following two:
$$A = \left[ {\begin{array}{ccc}
1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1
\end{array}}
\right]$$
and
$$B = \left[ {\begin{array}{ccc}
1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0
\end{array}}
\right]$$
They clearly share the eigenvector $(1,0,0)$, but the lower blocks of the matrices A and B are respectively the Pauli-$z$ and Pauli-$x$ matrices, which do not commute.

## Best Answer

For each pair (eigenspace for $A$, eigenspace for $B$), pick a basis for their intersection. (In particular, if an intersection is 0-dimensional, it will not have/contribute with any basis vectors.) Finally concatenate all the bases.