If $\nabla$ is any connection and $f$ a function, its Hessian with respect to $\nabla$ is $\mathrm{Hess}^{\nabla}f = \nabla \mathrm{d}f$, and one can see, after a messy calculation, that:
$$
\mathrm{Hess}^{\nabla}f(X,Y) - \mathrm{Hess}^{\nabla}f(Y,X) = \pm\mathrm{d}f\left([X,Y] - (\nabla_XY - \nabla_YX) \right)
$$
(where the $\pm$ sign is here because I don't remember the exact sign, but the computations are not that hard, just messy.) Hence, Hessians are symmetric if and only if the connection is torsion-free. This is the main motivation to consider torsion-free connections: in the euclidean space, Hessians are symmetric!
Moreover, the fundamental theorem of Riemannian geometry tells us that on a Riemannian manifold, there is a unique connexion that is torsion-free and lets the metric invariant, that is:
$$
\forall X,Y,Z, \left(\nabla_Zg\right)(X,Y) = Z\cdot g\left(X,Y \right) - g\left(\nabla_ZX,Y\right) - g\left(X,\nabla_ZY\right) = 0.
$$
(compare with the euclidean case, where $\langle X,Y\rangle ' = \langle X',Y\rangle + \langle X, Y' \rangle$.)
This theorem thus says that given any Riemannian metric $g$, there is a connection that is better than others: Hessians are symmetric and the metric is invariant under the action. We call it the Levi-Civita connexion.
If a connection is chosen, a geodesic is a parametrized curve satisfying the equation of geodesics : $\nabla_{\gamma'}\gamma' = 0$. Thus a curve $\gamma$ is a geodesic with respect to the connection, and can be a geodesic for some connection $\nabla^1$ but not for another connecion $\nabla^2$. Therefore, your question does not really have sense: we do not say that a connexion gives the least energy of a geodesic. I think you got confused, believing that being a geodesic is an intrinsic notion, but it really depends on the connection you consider.
Now, suppose $(M,g)$ is a Riemannian manifold endowed with its Levi-Civita connexion. Then if $\gamma : [a,b] \to M$ is a curve, we define its energy to be:
$$
E(\gamma) = \frac{1}{2}\int_a^b \|\gamma'\|^2
$$
and one can show that, in the space of all curves $\{\gamma : [a,b] \to M\}$ with same end points, a curve $\gamma$ is a point where the energy functional is extremal if and only if $\nabla_{\gamma'}\gamma'=0$, that is if and only if $\gamma$ is a solution of the equation of geodesics. Hence, a minimizer of the energy functional is a geodesic.
I will try to indicate how affine connections are related to Ehresmann connections.
Given a vector bundle $\pi:E\to M$ over a manifold, an affine connection is an operator
$$\nabla: \mathfrak{X}(M)\times \Gamma(M,E)\to \Gamma(M,E)$$
written as $\nabla(X,s)=\nabla_Xs$ which is $\Bbb{R}$-linear in both factors and satisfies the Leibniz property, i.e. for all $X\in \mathfrak{X}(M)$, $s\in \Gamma(M,E), f\in C^\infty(M)$,
$$
\nabla_X(f\cdot s) = X(f)\cdot s+f\nabla_X(s).
$$
On the other hand, an Ehresmann connection is defined as a right-invariant horizontal distribution $\mathcal{H}$ on a principal $G$-bundle, $p:P\to M$. In a certain sense, an affine connection is a special case of an Ehresmann connection. Associated to $E$ as above is its bundle of frames $\mathrm{Fr}(E)$, which is a fibre bundle whose fibre over $x\in M$ is $\mathrm{Fr}(E)_x$, the set of bases of $E_x$. Since $E_x$ is a vector space of dimension $r$ for all $x$, one proves that this is a principal $\mathrm{GL}_r(\Bbb{R})$-bundle. Indeed, any pair of bases of a vector space $V$ of dimension $r$ are related by a unique element of $\mathrm{GL}(V)$.
On the other hand, $\nabla$ is locally encoded by a connection $1$-form, which is a differential $1$-form which is valued in $\mathfrak{g} = \mathfrak{gl}(r,\Bbb{R})$. Indeed, choose an open set $U$ such that $E$ admits a local frame $e = \{e_1,\ldots, e_r\}$. Then, there is a unique matrix $(\omega_j^i) = \omega$ of differential $1$-forms such that for all $X$ and $j$
$$
\nabla_X e_j = \sum_i \omega_j^i(X)e_i.
$$
Under a change of frame, i.e. a map $g:U\to \mathrm{GL}(r,\Bbb{R})$, we get a new frame $e' = \{ge_1,\ldots, ge_r\}$. Write the connection $1$-form of $e$ as $\omega_e$ and that of $e'$ as $\omega_{e'}$. One has
$$
\omega_{e'} = g^{-1}\omega_e g + g^{-1}dg
$$
where $dg$ is $d(g)$, where $g$ is regarded as a matrix of smooth functions.
An Ehresmann connection $\mathcal{H}$ as above defines a $\mathfrak{g}$-valued $1$-form on $P$ by the exact sequence: for each $x\in P$, let $\mathcal{V}_x := \ker p_{*,x}$. Then
$$
0\to\mathcal{H}_x\to T_xP\to \mathcal{V}_x \to 0
$$
is exact. However, as $P$ is a principal $G$-bundle, $\mathcal{V}_x\cong \mathfrak{g}$ canonically, and we define a form $\omega:T_xP\to \mathcal{V}_x \cong \mathfrak{g}$ using the arrow in the exact sequence. Such an $\omega$ is $G$-invariant, satisfies $\omega(\underline{X}_x) = X$, where $\underline{X}_x$ is the vector field associated to $X\in \mathfrak{g}$ from differentiating the $G$-action, and smooth. Conversely, one can show that a $\mathfrak{g}$-valued $1$-form with those properties determines an Ehresmann connection, i.e. a right invariant horizontal distribution.
Anyway, an affine connection $\nabla$ defines parallel transportation of vectors in $E$. More precisely, given $\gamma:I=(-\epsilon,\epsilon)\to M$ such that $\gamma(0) = y$, then for a chosen frame around $y$ extending the basis $s_1(y),\ldots, s_r(y)$ of $E_y$, parallel transport gives a lift to a curve $\widetilde{\gamma}:I\to \mathrm{Fr}(E)$ with $\widetilde{\gamma}(0) = (s_1(y),\ldots, s_r(y)) =: s(y)$. There is an associated tangent vector $\widetilde{\gamma}'(0) \in T_{s(y)}\mathrm{Fr}(E)$. The set of all trajectories of such lifts along all $\gamma$ forms a vector subspace of $T_{s(y)}\mathrm{Fr}(E)$. One verifies that this is a right-invariant distribution on $T\mathrm{Fr}(E)$, giving us an Ehresmann connection.
So, an affine connection $\nabla$ on $E$ gives us an Ehresmann connection $\mathcal{H}$ on the associated frame bundle, $\mathrm{Fr}(E)$. This has the following beautiful property (though it is really a tautology once you unwind the definitions).
Note that choosing a frame $e$ on an open set $U$ of $M$ is equivalent to giving a section $e:U\to \mathrm{Fr}(E)|_U$ of the projection $p$.
Theorem: Let $\nabla$ denote an affine connection on $E$ and let $\omega$ denote the $\mathfrak{g}$-valued $1$-form given by the associated Ehresmann connection on $\mathrm{Fr}(E)$. Given any choice of local frame $e:U\to \mathrm{Fr}(E)|_U$, we have $e^*\omega =\omega_e$.
Here, $\omega_e$ is the matrix of $1$-forms from further up in the post. The upshot of all this is that an affine connection is represented locally by a matrix in a local frame, while an Ehresmann connection is like "working in all frames at once." (so says a friend of mine, anyway!)
I learned most of what I know about this from Tu's book Differential Geometry: Connections, Curvature, and Characteristic Classes, which I highly recommend.
Best Answer
For those who come across this question, an explicit answer is handled in depth in the Kobayashi’s foundations of differential geometry. In the special case where $E$ is the tangent bundle, one can think of it as a vector bundle associated to the bundle of orthonormal frames of $TM$. One can then construct a notion of torsion in the frame bundle, and we can find a torsion free, metric compatible connection one form in the bundle of orthonormal that corresponds to the Levi-Civita connection.