I am extremely confused about the exact difference between a vector and a covector. For instance:
Let a curve $\gamma : \mathbb{R} \rightarrow M$ be a smooth curve through a point $p \in M$, where $M$ is a manifold. Then the directional derivative operator is the linear map:
$X_{\gamma, p} : C^{\infty} (M) \rightarrow \mathbb{K}$,
where $\mathbb{K}$ is the underlying ring. Now, all books I have seen on higher geometry states that this a vector and that the operator can be written as $X_{\gamma, p} := e_i f$, despite the fact that is seems to behave like a covector (i.e. mapping an element from $C^{\infty}$ into the underlying ring)? Likewise, everyone agrees that any $X \in T_p M$, where $T_p M$ is the tangent space for $p \in M$, can be written as
$X= \sum_{i} x^i e_i$,
where $x^i \in \mathbb{K}$. In other words: Clearly a covector, judging from the notation. However, the gradient operator $d_p$ is said to be a covector, and a map $d_p : C^{\infty} (M) \rightarrow T_p^{\ast}(M)$, where $T_p^{\ast} M$ is the cotangent space. This defintion seems redundant, since any $X \in T_p M$ is already a map $C^{\infty}(M) \rightarrow \mathbb{K}$?
Can anyone clarify these concepts? What is the relationship between the tangent vectors, the gradient etc.?
It seems you are confused by the notation? As you pointed out, the tangent space of a point can be seen as the space of directional derrivatives with evaluation at that point. The cotangent space (space of differential forms at the point) is just the dual vector space in the sense of linear algebra. So covectors map vectors to numbers. From the sense of linear algebra you can form the dual space of any vector space. In particular the tangent space can be the space of derrivations, as you described.
Now you are right in that $C^{\infty}(M)$ is a vector space, in fact it is even a ring. But the space $T_pM$ is NOT the dual space of this. That is: Only a small part of the mappings $C^{\infty}(M)\to \mathbb{K}$ are actually vectors at points of $M$. They have to satisfy the Leibnitz-rule: If $V\in T_pM$ then for all $f,g\in C^{\infty}(M)$ (you could also take equivalence classes of functions equal on a neighbourhood of the point instead) \begin{equation} V(f\cdot g)=V(f)g(p)+f(p)V(g) \end{equation}
In general, the space of vetor fields is a module over the ring $C^{\infty}(M)$. This way you can try to carry over some of the linear algebra from the tangent space at a point to more global constructions.
In the notation you used, the $e_i$ are basis vectors of the space $T_pM$. Hence a linear combination of those is a vector. In case you are confused by the index placement (otherwise ignore the following): In the notation the components of vectors receive upper indices. The basis vectors have indices down, so the components can be contracted with them avoiding summation signs.
Gradients are usually thought of as vectors. If you have a metric (a symmetric bilinear form, depending on what else you have (Riemanian) also positive definite, which varies smoothly from one tangent space to others) $g:T_pM\times T_pM\to \mathbb{K}$, you can convert covectors into vectors by assigning a vector $V$ to the covector, which maps $T_pM\ni W\mapsto g(V,W)$. Thus the metric induces a mapping $T_pM\to T^*_pM$ which is called "musical isomorphism". This map can be inverted and thus any covector can be converted into a vector via the metric, too. The gradient of a function $f\in C^{\infty}(M)$ at the point $p$ is the vector that you get, when you convert the covector $d_pf$ into a vector. That being said, the covetor $df$ contains the information we usually associate with a gradient in classical vector analysis. For most uses where you would use the gradient you don't actually need or want it to be a vector (every time you "dot" the gradient into something). Thus you could also see $df$ as "the correct way to think about the gradient", as long as you don't forget it's not a vector.