First let me say that what is intuitive to a physicist may be not be so to a geometer and vice-versa. To many physicists a connection is the potential of a field satisfying a gauge invariance. For this point of view I refer to vol. 1, Chap. 6 sect 41 of the three volume book by Dubrovin-Fomenko-Novikov: Modern Geometry-Methods and applications.
I find this point of view less intuitive only because I was trained as a mathematician.
The notion of covariant derivative appears naturally when one tries to solve the following problem. Suppose that $E\to M$ is a smooth vector bundle over a smooth manifold $M$. For example, $E$ could be the tangent bundle of $M$. We seek a notion of parallel transport that will allow us to compare vectors situated in different fibers of the bundle. More precisely, this is a correspondence that associates to each smooth path
$$\gamma: [a,b]\to M$$
a linear map $T_\gamma$ from the fiber of $E$ at the initial point of $\gamma$ to the fiber of $E$ over the final point of $\gamma$
$$T_\gamma: E_{\gamma(a)}\to E_{\gamma(b)}.$$
The map $T_\gamma$ is called the parallel transport along the path $\gamma$.The assignment $\gamma\mapsto T_\gamma$ should satisfy two natural conditions.
(a) $T_\gamma$ should depend smoothly on $\gamma$. (The precise meaning of this smoothness is a bit technical to formulate, but in the end it means what your intuition tells you it should mean.)
(b) If $\gamma_0: [a,b]\to M$ and $\gamma_1:[b,c]\to M$ are two smooth paths such that the initial point of $\gamma_1$ coincides with the final point, then we obtain by concatenation a path $\gamma:[a,c]\to M$ and we require that
$$T_\gamma= T_{\gamma_1}\circ T_{\gamma_0}. $$
Suppose we have a concept of parallel transport. Given a smooth path $\gamma:[0,1]\to M$ and a section $\boldsymbol{u}(t)\in E_{\gamma(t)}$, $t\in [0,1]$ of $E$ over $\gamma$, then we can define a concept of derivative of $\boldsymbol{u}$ along $\gamma$. More precisely
$$ \nabla_{\dot{\gamma}} \boldsymbol{u}|_{t=t_0}=\lim_{\varepsilon \to 0} \frac{1}{\varepsilon} \left( T^{t_0,t_0+\varepsilon}_\gamma \boldsymbol{u}(t_0+\varepsilon)- \boldsymbol{u}(t_0)\right), $$
where $ T^{t_0,t_0+\varepsilon}_\gamma$ denotes the parallel transport along $\gamma$ from the fiber of $E$ over $\gamma(t_0+\varepsilon)$ to the fiber of $E$ over $\gamma(t_0)$. The left-hand-side of the above equality is called the covariant derivative of $\boldsymbol{u}$ along the vector field $\dot{\gamma}$ determined by the parallel transport. Thus, a choice of parallel transport leads to a concept of covariant derivative.
Conversely, a covariant derivative $\nabla$ leads to a parallel transport. Given a smooth path $\gamma:[0,1]\to M$ the parallel transport
$$T_{\gamma}: E_{\gamma(0)}\to E_{\gamma(1)} $$
is defined as follows. Fix $u_0\in E_{\gamma(0)}$. Then there exists a unique section $\boldsymbol{u}(t)$ of $E$ over $\gamma$ satisfying
$$ \boldsymbol{u}(0)=u_0,\;\;\nabla_{\dot{\gamma}}\boldsymbol{u}(t)=0,\;\;\forall t\in [0,1].$$
We then set $\newcommand{\bu}{\boldsymbol{u}}$
$$T_\gamma \bu_0:= \boldsymbol{u}(1).$$
This construction allows us to define the covariant derivative $\nabla_X\bu$ of a section $\bu$ of $E$ along a vector field $X$ of $M$. It satisfies the rescaling property
$$ \nabla_{fX}\bu=f\big(\nabla_X\bu\big),\;\;\forall f\in C^\infty(M). $$
A connection on $TM$ will then satisfy
$$\nabla_{fX} Y=f\big(\nabla_X Y),$$
for any vector fields $X,$ and any smooth function $f$. On the other hand the Lie derivative satisfies
$$
L_{fX} Y= fL_XY-(Xf) Y,
$$
so it cannot be a covariant derivative.
