> Does the vector potential $A_\mu$ transform when we merely relabel events in space-time (coordinate transformation), or does it transform with the basis vectors of a tangent space in which it lives?

$A_{\alpha}$ by the definition is an lorentz covariant vector, so transformations in spacetime like lorentz boosts ($\Lambda^{\beta}{}_{\alpha}
x^\alpha$) doesn't change $A_\alpha$.

> is there any difference between stating that we always have to transform the tangent space with the coordinates, and just saying that $A_\mu$ transforms with the coordinates?

*If i understand it correctly*, you're asking if in curved coordinates which tangent spaces varies, $A_{\alpha}$ will transform too. Well, *locally* no (i guess). However, the 1-form field $A=A^{\alpha}e_{\alpha}$ with tangent basis $e_{\alpha}$, has a curvature form $F$ defined by $F=dA$ where $dA$ is the exterior derivative of the 1-form $A$, in indice notation $F=dA$ can be rewrite as $F_{\alpha\beta}={\partial}_{\alpha}A_{\beta}-{\partial}_{\beta}A_{\alpha}$, which is the electromagnetic tensor. in curved coordinates the $\partial_{\alpha}$ transforms to the Einstein's covariant derivative $\nabla_{\alpha}$.

> Since it is part of the covariant derivative $\partial_\mu−ieA_\mu$ and the gauge transformation goes like $A_\mu \to A_\mu + \partial_\mu \lambda$, I would think it should transform with the coordinates, as does $\partial_\mu$. I don't see how the gauge transformation can be consistent if $A_\mu$ and $\partial_\mu \lambda$ don't transform in the same way.

the covariant derivative is an object in QFT's constructed to make field lagrangians invariant under some groups transformations. For example, in QED, the symmetry group is $U(1)$ which generates a local phase change in matter fields, and to avoid "unphysical" local terms in the lagrangian, is introduced an "fixed local derivative" (or covariant derivative) $D_\mu=\partial_\mu - ieA_\mu$ that makes the theory *locally invariant*. 
 Also not only the matter field gauge-transforms, the introduced $A$-field transforms like $A_\mu+\partial_\mu \lambda$.


I know that's a bad explanation, so i recommend you read this [Wikipedia's article](https://en.wikipedia.org/wiki/Covariant_derivative) to a more detailed answner.