So, I can now explain almost all the material that confused me. I don't know if this will help anyone else, but here is the answer that would have helped me.
Let $M$ be a manifold with a connection on $T_* M$. Let $\gamma: [0,1] \to M$ be a curve in $M$. Then parallel transport gives us maps $g_t: T_{\gamma(0)} M \to T_{\gamma(t)} M$. So we get a vector $g_t^{-1} \gamma'(t)$ in $T_{\gamma(0)} M$ for every $t$. Let $b(u) = \int_0^u g_t^{-1} \gamma'(t) dt$. So $b(u)$ is a path in $T_{\gamma(0)} M$.
The physical meaning of $b(u)$ (when $\nabla$ is the LC conection) is that, if we roll $M$ along a table, so that at time $t$, $M$ is tangent is the table at position $\gamma(t)$, then $b(u)$ is the path traced on the table by the tangency point. The affine linear map in my question is more or less $v \mapsto g_t (v + b(t))$. See Bill Thurston's answer for physical intuition underlying this.
I believe that the statement which Hehl and Obukhov intended was the following:
Let $\gamma$ be a small curve, bounding a "disc of size $r$", for some small $r$. If $\nabla$ is torsion free then $b(1) = O(r^3)$. Otherwise, if $\gamma$ is in "the plane spanned by the vectors $X$ and $Y$", then $b(1) = T(X,Y) r^2 + O(r^3)$, where $T$ is the torsion tensor and I might be missing some factors of $2$ or $\pi$.
Here the phrases in quotes are meant to be nonrigorous: the disc could be a square or an oval rather than a perfect circle, and I don't claim to have a definition of "plane" in a general Riemmannian manifold. The point is that we should be should be working locally enough that our Euclidean intuition for these concepts is adequate.
Let's do some sanity checks. First, let's work on $\mathbb{R}^n$ with a constant connection, meaning that
$$\nabla_{\partial_i} \sigma = \partial_i(\sigma) + A_i \sigma,$$
where $A_i$ is a constant $n \times n$ matrix. (It must be skew-symmetric, in order to have $\nabla$ respect the metric.) Let's go around a square in the $\mathbb{R}^2$ plane; traveling $r$ in direction $e_1$, $r$ in direction $e_2$, $r$ in direction $-e_1$ and $r$ in direction $-e_2$. So the path $b$ consists of four segments of length $r$, in directions
$$e_1,\ e^{-r A_1} e_2,\ -e^{-r A_1} e^{-r A_2} e_1 \ \mbox{and} \ -e^{-r A_1} e^{-r A_2} e^{r A_1} e_2.$$
The total displacement is
$$r((e_1+e_2-e_1-e_2)-r(A_1 e_2 + A_1 e_1 + A_2 e_1 + A_2 e_2) + O(r^2))$$
$$=r^2(A_1+A_2)(e_1+e_2)+O(r^3).$$
Intuitively, we are adding up four vectors of length $r$. They can be grouped into two nearly antiparallel pairs; in each pair, the angle between a vector and its near-negative is $O(r)$. So the sum in each pair is $O(r^2)$, and there is no reason to expect further cancellation.
For our second sanity check, let's look at the LC connection on $S^2$ (of radius $1$). This has no torsion, so we should be able to see that.
Let's roll the sphere, keeping the contact point on a line of constant latitude $\phi$. (Here $\phi \in (0, \pi)$, with $\pi/2$ meaning the equator.) The path $b$ is an arc of a circle. The arc has radius $\tan \phi$, and sweeps out the angle $2 \pi \cos \phi$. So the distance from one end of the arc to the other is $2 (\tan \phi) \sin\left( \pi \cos \phi \right) = 2 O(\phi) \sin (\pi - O(\phi^2)) = O(\phi^3)$. So we see that the displacement goes to $0$ as $O(\phi^3)$, as desired.
In response to Bill Thurston's request for pictures, here are the paths traced by the ball for $\phi=(0.1 \ \mbox{radians})*k$, with $1 \leq k \leq 7$. Note that the radii of the arcs are shrinking linearly, but the gap between the endpoints of the arc is shrinking cubicly.
So, let me now try to address my confusion in part (2), using the example of $S^2$. I was confused by two things. The first is that I took the authors to be saying the translation would vanish, when in fact it died off like $O(r^3)$. But the second was that I had a fallacious argument in my head suggesting that, if we had an $O(r^3)$ bound, then it would imply that the displacement $b$ around any contractible loop would be zero. I don't know if this will help anyone else, but I will now spell out the fallacy and expose it.
False Proof: Identify my contractible path $\gamma$ with a square of side length $1$. Subdivide it into $N^2$ little squares $s_1$, $s_2$, ..., $s_{N^2}$. Let $p$ be a corner of the big square. Let $\delta_i$ be a path which goes from $p$ to $s_i$, circles $s_i$, and goes back to $p$. Let $\delta$ be the concatenation of the $\delta_i$'s. If you choose the ordering of the $s_i$'s correctly and choose the right $\delta_i$'s, then $\delta$ is simply $\gamma$ with a whole lot of backtracking put in.
So the path $b_{\delta}$ coming from $\delta$ will simply be $b_{\gamma}$, plus a lot of backtracking segments. So $b_{\gamma}$ is a concatenation of $N^2$ paths, each of length $O(1/N^3)$. We see that the length of $b_{\gamma}$ is $O(1/N)$. Since $N$ was arbitrary, this concludes the fallacy. QFD
This is similar to a (correct) proof that, if $\omega$ is a closed one-form, then $\oint \omega$ around any contractible loop is $0$: You directly compute that, for a closed one-form, $\oint_{r \cdot \gamma} \omega = O(r^3)$ and then run a similar subdivision argument.
So, why doesn't this work? Going around $s_i$ really does only contribute $O(1/N^3)$. But going from $p$ to $s_i$, around $s_i$, and back to $p$ contributes $O(1/N^2)$! The reason is that, because of curvature, the trip around $s_i$ rotates my reference frame. Thus, when I travel back the way I came, the resulting path is rotated and does not backtrack along itself. How large is this effect? The angle of rotation is $2 \pi - O(\mathrm{Area}(s_i))$, which can be treated as $O(\mathrm{Area}(s_i))$ since we only care about the net effect and not the winding number. The area is $O(1/N^2)$. So we travel a path of length $O(1)$, and then backtrack along the rotation of that path through an angle of $O(1/N^2)$. So our net displacement is $O(1/N^2)$, and the fallacy falls apart.
Here are some figures of taking a ball which is resting on its equator, rolling it to latitude $\phi$, once around at latitude $\phi$, and back the the equatorial starting point. The values of $\phi$ are $0.1$, $0.2$ and $0.3$ radians. What you are supposed to see is that the radii of the arcs are dropping linearly, the separation between the endpoints of the arcs is dropping cubically, and the separation between the end points of the spokes is dropping quadratically.