How is it that adding a random field to the partial derivative results in a tensorial operation? We know that the partial derivative of a tensor is not a tensor. But how is this problem fixed by adding to the partial derivatives, a field of Christoffel symbols? Christoffel symbols are a completely arbitrary field because you can define any arbitrary connection you want. How is it that adding a completely arbitrary field fixes the problem, and that the resultant covariant derivative transforms as a tensor?
 A: 
Christoffel symbols are a completely arbitrary field
because you can define any arbitrary connection you want.

No, the Christoffel symbols are not arbitrary. They are defined
(see Christoffel symbols - Definition in  Euclidean space)
by how the base vectors $\mathbf{e}_i$ depend on the coordinates $x^j$.
$$\frac{\partial\mathbf{e}_i}{\partial x^j} = \Gamma^k_{ij}\ \mathbf{e}_k$$
or equivalently
$$d \mathbf{e}_i = \Gamma^k_{ij}\ \mathbf{e}_k\ dx^j \tag{1}$$
It is this definition, from which you can derive that
for a tensor field $A^i$ the expressions
$$\frac{\partial A^i}{\partial x^j}+\Gamma^i_{jk}\ A^k$$
are components of a tensor, while the partial derivatives
$$\frac{\partial A^i}{\partial x^j}$$
are not.
You can derive this in a straight-forward way
by starting with the invariant differential
$d\mathbf{A}$ of a vector field between two positions in space.
$$\begin{align}
d\mathbf{A} &= d(A^i\ \mathbf{e}_i) \\
 &= dA^i\ \mathbf{e}_i + A^i\ d\mathbf{e}_i
 & \text{use definition (1)} \\
 &= \frac{\partial A^i}{\partial x^j} dx^j\ \mathbf{e}_i
    + A^i\ \Gamma^k_{ij}\mathbf{e}_k\ dx^j
 & \text{in the second term swap indices $i$ and $k$} \\
 &= \frac{\partial A^i}{\partial x^j} dx^j\ \mathbf{e}_i
    + A^k\ \Gamma^i_{kj}\mathbf{e}_i\ dx^j \\
 &= \left( \frac{\partial A^i}{\partial x^j}+A^k\ \Gamma^i_{kj} \right) \mathbf{e}_i\ dx^j 
\end{align}$$
or equivalently
$$\frac{\partial\mathbf{A}}{\partial x^j} =
\left( \frac{\partial A^i}{\partial x^j}+A^k\ \Gamma^i_{kj} \right) \mathbf{e}_i$$
You see, the covariant derivative emerged as the components of
$\partial\mathbf{A}/\partial x^j$ in a quite natural way.
