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

$$T_\gamma u_0:= \boldsymbol{u}(1).$$