Why do we need connections, if we have the Lie derivative? When I learned about the covariant derivative, it was motivated as a way of defining a good differentiation operation on tensors. To do this, we had to define a connection on the manifold, which was a substantial extra piece of structure.
However, the Lie derivative requires no connection at all; it just requires a vector field $V^\mu$ defined on the manifold. In particular, since we've already chosen coordinates, we can define the Lie derivative in any direction $n^\mu$ by using the vector field $V = n^\mu \partial_\mu$, which requires zero extra structure. Then $\mathcal{L}_V$ seems to be a perfectly good replacement for $n^\mu \nabla_\mu$.  At the very least, it does everything that books say the covariant derivative was meant to do. Ignoring all the stuff the covariant derivative ends up getting used for, I don't know why we would have introduced it in the first place.
What good properties does $n^\mu \nabla_\mu$ have that $\mathcal{L}_{n^\mu \partial_\mu}$ does not?
 A: One distinctive feature is that the connection $\nabla$ has the tensor field property in its first entry $\nabla_{fX}=f\nabla_{X}$, while the Lie derivative doesn't. We have ${\cal L}_{fX}\neq f{\cal L}_{X}$ generically. 
There are already manifestly covariant explanations on Math.SE and Mathoverflow.SE. Let's for simplicity consider a local coordinate patch $U$ with coordinates $x^{\mu}$. The tensor field property implies that the covariant derivative $\nabla_{X}=X^{\mu}\nabla_{\mu}$ is completely determine by some directional derivatives $\nabla_{\mu}$. Not so for the Lie derivative. 
Say that we are given a metric tensor field $g$ and some tensor field $T$. Assume for simplicity that the tensor field components $g_{\mu\nu}$ and $T^{\mu_1 \ldots \mu_r}{}_{\nu_1 \ldots \nu_s}$ in the given local coordinate system are constant, i.e. $x$-independent. Let $\nabla$ be the Levi-Civita connection. Then $\nabla_Xg=0$ and $\nabla_XT=0$ as we would expect from a directional derivative (since after all, the tensor field components are constant in one coordinate system). But ${\cal L}_{X}g\neq 0$ and ${\cal L}_{X}T\neq 0$ generically.
