Is this the correct intuition behind the covariant derivative? If not can you please show me how to covariant derivative is related to the directional derivative?
The covariant derivative can be thought of as a generalisation of the directional derivative to non Euclidean spaces. The directional derivative is a mapping which takes as input some tangent vector at a point $p\in \mathbb{R}^n$ and a scalar field $f(x^1, x^2,....,x^n)$ and returns a real number. Since we are working in $\mathbb{R}^n$ we can acknowledge that there exists a map $F: \mathbb{R}^n \to \mathbb{R}^n$ which is to be considered a vector field. Due to the geometry of $\mathbb{R}^n$ we can think of points as vectors and vectors as points and hence the directional derivative acting on scalar fields can naturally be thought of as acting on vector fields. However for a general manifold M, the notion of a derivative acting on vector fields does not arise naturally from that of a derivative which acts on functions, the reason being that we cannot assign to each point $p\in M$ a 'tangent vector in $M$' due to the fact that a vector field in one coordinate chart will not be consistent with a vector field in some other chart. In general the basis of tangent space at $p\in M$ is different to that of $q\in M$, a connection provides a way of relating the two tangent spaces in such a way that permits vector fields to be differentiated in a way that is consistent with notion of the directional derivative on $\mathbb{R}^n$.
Your intuition is essentially correct. In $\mathbb{R}^n$ the tangent spaces $T_p$ and $T_q$ at two different points is the same $\mathbb{R}^n$ so we have no problem in defining the directional derivative staring from the vectors tangent to a field at two different points in the same direction.
In a manifold these two tangent space are, in general, different, so we don't have a well defined ''direction'' in two different tangent space. A connection is a rule that connects the two tangent spaces and defines in what sense the two vectors have the same direction. So, using the connection we can define the variation of the tangent vector at two points and define the covariant derivative.
Note that the connection is a structure that is not given by the structure of the manifold, but it is added and, for the same manifold, we can have different connections. If there is a metric on the manifold, we can define in a ''natural'' way a connection that is compatible with the metric.