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
The second one is the correct viewpoint. Given a Hamiltonian $H$ and another hermitian operator $S$, which commute you can find a simultaneous eigenbasis for both operators. Let's call them $|n,s>$. Acting on these states with $H$ we have $H|n,s>=E_n|n,s>$ for some value(s) of $s$, which means that the eigenspace for the eigenvalue $E_n$ might be more than one-dimensional: $\dim(V_{E_n})=\# \text{Allowed Values of s}$. If this is the case, this means degeneracy regarding the H-Op.
Given any hamiltonian and hilbertspace there is no way by finding other operators to reduce the dimensionality of the eigenspace of $H$. The dimensionality is an algebraic property of $H$ itself.
However, if there is a degeneracy, it is very useful to find an operator, which commutes with $H$, to classify the degeneracy i.e. to learn about it and also to get control about the degenerate eigenspaces i.e. to find a basis in the eigenspaces labelled by a conserved quantum number (eigenvalue of an operator, which commutes with $H$).