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.