Two operators may be simultaneously diagonalized if and only if they commute.
As you can see, $L_z$ commutes neither with $L_x$ nor with $L_y$ – and not with any other linear combinations different from a multiple of $L_z$ – so there's no way to diagonalize two different components of $L_i$ at all.
However, $L_z$ (and similarly other components) commutes with $L^2$, so $L_z$ and $L^2$ may be simultaneously diagonalized.
It means that whatever basis you have and $L_z,L^2$ expressed with respect to this basis, one may find a matrix $U$ on the Hilbert space such that both $UL^2 U^{-1}$ as well as $U L_z U^{-1}$ are diagonal matrices. No other component etc. may be added. We say that $L^2,L_z$ form a "complete set of commuting observables" describing the angular part of the wave function of one particle (or all the internal angular momentum, spin degrees of freedom of any particle).
You reach something like a "paradox" by discussing eigenspaces. The problem with your reasoning is that the eigenspaces are multi-dimensional in most cases but they are not subspaces of each other.
$L^2$ has different eigenvalues $\ell(\ell+1)\hbar^2$ for $\ell=0,1,2,3,\dots $ Also, half-integer values are possible for the general "spin".
But if you consider the full Hilbert space, the eigenspace corresponding to the eigenvalue with $\ell$ is not one-dimensional. Instead, it is at least $(2\ell+1)$-dimensional. It is exactly this-dimensional if there are no other degrees of freedom. If there are other degrees of freedom, the dimension of the eigenspace is a multiple of $(2\ell+1)$.
On the other hand, the eigenspace of $L_z$ is associated with the eigenvalues of this operator, $m$. You may get the eigenvalue $L_z=m$ for $\ell = |m|$ but you may also get it for $\ell=|m|+1$, $|m|+2$, or any other number greater than $|m|$ by a positive integer. So the eigenspace of $L_z$ is the linear envelope of the union of one-dimensional subspaces of eigenspaces of $L^2$.
The eigenspace of $L_x$ corresponding to the eigenvalue of $m$ picks different one-dimensional subspaces from those. Their basis vectors are neither parallel nor orthogonal to those associated with $L_z$. Similarly for $L_y$.
The multi-dimensional eigenspace of $L^2$ with the eigenvalue $\ell(\ell+1)\hbar^2$ and the multi-dimensional eigenspace of $L_z$ with the eigenvalue of $m$ have an intersection – in the simplest case of wave functions on the sphere, one-dimensional intersection – that corresponds to all states with the eigenvalues given by the quantum numbers $(\ell,m)$.