Confusion re: geodesics, connections, and straightness In my readings in GR I often come across geodesics characterized as "straightest possible curves." This characterization confuses me. I'd like some clarification as to whether I'm understanding the math concepts correctly.
To fix ideas, my understanding of the basic math of GR is that we can start with a connection, which lets us map a vector in a tangent space to a vector in a nearby tangent space and stipulate that these two vectors count as "the same." This in turn allows us to calculate how a vector field changes in a way that corrects for using different coordinate systems, i.e. the covariant derivative. This in turn lets us define the parallel transport of a vector along a curve. This in turn lets us characterize geodesics and investigate the curvature of the space. (I recognize there are other ways to develop these concepts depending what you start with, but this is most intuitive to me. Hopefully it's correct.)
Now, my understanding of geodesic curves is that they are those whose tangent vectors do not change as we move in the direction of the tangent vector itself. I.e. they parallel transport their tangent vectors. 
My question is how this 'parallel transporting its tangent vector' is equivalent to a curve which does so being 'straightest possible.' My understanding is that straightness depends on parallel-ness, which depends on the connection, whicn is not given but something i can choose. So this meant that by choosing a certain connection, i decide what is 'straight'. 
But if that is so, what are the constraints that make one kind of curve -e.g. a great circle on a sphere- the 'straightest possible'? 
What's to prevent me from defining literally any curve on a sphere and then choosing a connection such the tangent to that curve is thereby defined as parallel to the tangent at the previous point and thereby defining that curve as straight by fiat? 
And if i can do that, on what grounds can it be said that a great circle is "straighter" than the curve i have thus defined as straight by construction? 
 A: 
This is the variational approach to defining geodesic trajectories, yes? I'm aware of it but haven't studied with care. Does that approach require a metric? I am trying to steer away from definitions of these things that require a metric for now. Maybe that is part of my confusion[...]

That's right.
As you say, a connection defines a covariant derivative, which provides us with a notion of parallel transport.  This allows us to talk about autoparallel curves, which we colloquially call straight.  This has nothing whatsoever to do with distances.
On the other hand, a metric defines a notion of distance on a manifold, which allows us to consider whether or not the length of a curve is stationary with respect to small perturbations (leaving the endpoints fixed).  Such curves are called geodesics, and have nothing whatsoever to do with straightness.
These structures are independent in principle.  However, if we demand that the connection $\nabla$ be metric compatible (so the covariant derivatives of the metric vanish) and torsion-free, then we arrive at the unique Levi-Civita connection$^*$; in this case, it can be shown that the autoparallels and geodesics coincide$^{**}$.

$^*$See the Fundamental Theorem of Riemannian Geometry.
$^{**}$Note that we don't need to choose the Levi-Civita connection for this to be true - it actually suffices to choose a metric-compatible connection whose contorsion tensor is merely antisymmetric, rather than vanishing.
A: As an addition to J. Murray's already excellent answer.

My understanding is that straightness depends on parallel-ness, which
  depends on the connection, whicn is not given but something i can
  choose. So this meant that by choosing a certain connection, i decide
  what is 'straight'.

The connection is  part of the definition of your geometry. Changing the connection also means you are changing the curvature. In this sense it is not something you are free to choose, in the same way that your are for example free to choose coordinates. It is something that defines the structure of the space you are dealing with.
So when people say that geodesics (or autoparallel curves) are the straightest possible curves, they mean the straightest possible curves in a given geometry, meaning given a certain connection.
In most contexts of general relativity, the connection is taken to be the Levi-Civita connection compatible with a given metric (J. Murray's answer gives some context to why this makes sense). Consequently, giving a metric is usually intrerpreted as also specifying a connection.
