Why does the Palatini formalism of GR work? We can get the Einstein field equations of GR from the Einstein-Hilbert action via two distinct methods: 
First, by taking the metric as the only degree of freedom, and imposing right away that the connection is the Levi-Civita connection. In that case the Lagrangian will be a functional of the metric only since the Levi-Civita connection is expressible in terms of derivatives of the metric. 
Second, we can follow the Palatini method: Take the metric and the connection as independent degrees of freedom and vary with respect to both. It happens curiously that the Euler-Lagrange equations for the connection will just be the condition that it must be the Levi-Civita connection. 
It seems to be a wonderful coincidence that we get exactly the condition that the connection must be Levi-Civita one, thus recovering the Einstein field equations. So my question is: Why does this work? Is there any deeper mathematical reason why we get the right answer?
 A: The deep mathematical mechanism behind this is Cartan geometry. In Cartan geometry all geometric structures in manifolds (Riemannian, pseudo-Riemannian, complex, holomorphic, conformal, etc.) are expressed in terms of G-structures with integrability conditions, which in first order is torsion freedom.
The first order formulation of gravity that you are are referring to witnesses the fact that the Cartan-geometric description of pseudo-Riemannian geometry is equivalent to the one in terms of symmetric rank-2 tensors.
The same still applies to supergravity, its usual first-order formulation expresses super-Riemannian structure in terms of super-Cartan geometry. In fact higher dimensional supergravity is expressed in terms of higher Cartan geometry (to take the higher form fields into account).
Here is a little known fact in this context (Candiello-Lechner 93): generally the equations of motion of first-order (super-)gravity imply that (the bosonic component of) the (super-)torsion vanishes. But for 11-dimensional supergravity this implication goes the other way around: just requiring the (bosonic component of the) super-torsion to vanish is here already equivalent to the equations of motion. (Requiring the full supertorsion to vanish is equivalent to the bosonic Einstein equations in 11d!) Hence in 11d we may do away with the Palatini action and simply require torsion-freedom.
