How does one (physically) interpret the relationship between the graviton and the vielbein?

I'm mostly addressing the "thinking about gravity as a gauge theory" part of the question.

Gravity is a $SO(3,1)$ gauge theory with two independent gauge fields, the vierbein and the spin connection.

Roughly speaking, there are two ways to think about gravity as a (classical) field theory, which sort of underlies two different ways of implementing local $SO(3,1)$ invariance. In the Einstein approach, we right down the metric tensor $g_{\mu\nu}$ and reason that it is invariant. In the tetrad/vierbein formulation (sometimes called the Cartan approach), we right down the frame field $e^a$ and the spin connection $\omega^a_b$ (a 1-form gauge field) and demand that physics is invariant under $SO(3,1)$ transformations of these quantities. This second picture is much more analogous to how we define, for instance, Yang-Mills theory, albeit with two gauge fields for gravity.

This was all classical field theory. More broadly, there are many equivalent ways to write down the Einstein-Hilbert action (e.g. Palatini action for the frame field and spin connection, but see Sec. 3 of this review for many more). More to your question, I'm sure depending on the problem different people will prefer different formulations for doing perturbation theory, I'm not sure if one is more physical (there will always be two physical polarizations of the graviton, plus gauge degrees of freedom). Although it may be interesting to note though that Dirac spinors couple directly to the frame field in the action.

So your first equation is more general than the linearised version of the second equation, so let's focus on the most general relation.

In general your vielbein $e^\mu_a(x)$, depend on the coordinates of your manifold. So vielbein represent a local frame transformation away from flat space. And this phenomenon, after using the geodesic equation is what we call gravity.
The upshot is that the vielbein contains all the degrees of freedom of the graviton so sometimes it is called the graviton in the litterature. And obviously in linearised gravity, the dofs are contained in $h_{\mu \nu}$ so we call this one the graviton.

Now to interpret in terms of quantum, well that's a tall order. Like you said it is the gauge field of gravity and it is a spin-$2$ particle in terms of representation of the Lorentz group, which is a subgroup of Diff($M$).

edited my mistake about the large group of diffeomorphism (thanks to reading madmax's comment)