Wigner always complained about people who used the word « invariant » (this was, of course, in the context of Special Relativity): he said one should say that the principle of relativity requires « covariance,» not invariance.  Einstein's own papers on GR tend to carry out Wigner's request: the theory of GR (which is more general than Einstein's theory of gravity or his field equations) is always expressed as the demand for covariance with respect to arbitray coordinate changes.  Now another myth, according to me, is that relativity requires that the laws be transformed by the group into other laws « of the same form.»  This is just verbiage until you define what you mean by « form,» and even worse, it would then be just linguistics instead of physics.  Examining Einstein's practice in this matter, and his occasional explicit pronouncements, GR really says: the laws of physics must take the form of equating a tensor to zero.  This works because the tensor has the same covariance properties under change of coordinates as zero does.

Therfore the requirement of covariance has nothing to do with $f^* g$ for $f$ a diffeomorphism and $g$ a tensor field.  This can be seen another way: for Einstein, $M$ is not physical, it is $g$ that is physical.  Hence $f$ has to be regarded as a change of coordinates which does not actually move the mathematical points of $M$.  The formula which mathematicians use for $f^*g$ has to be reinterpreted as coming from $f$ as the transition function between two charts of $M$ around a given point $x$, i.e., qua diffeomeorphism, it is the identity.  Let me put this another way: a change of coordinates does not move the points, it just changes the charts.  Therefore, a change of coordinates is the trivial identity map when you look at it in the mathematicians' invariant, coordinate free definitions of $M$, $f$, $f^*$, and tensors.

And now let me put this a third way, tying it up with Wigner's point of view in Special Relativity: what GR requires is that $g_{\mu\nu}$ be covariant, and in your set-up, this is the requisit for $f^* g$ to *even be well-defined*.  This is what is needed to define a group action of diff($M$) on the set of metric tensors, and is the strict analogy to Wigner's requiring that one work with a representation of the Lorentz group.  Covariance means the group action is defined, not that it is trival.
 
That is one reason why diff($M$) is not a good analogy to the gauge transformations of EM or Weyl's theory.  But there is another: in EM, the relation between the potential and the field is one thing, but the relation between $g_{\mu\nu}$ and the Christoffel symbols (the affine connection) is quite another.  Yes, mathematically the two relations have something similar but from the stanpoint of the symmetries involved there is a crucial difference: the metric field is covariant (a tensor) but the Christoffel symbols are not, whereas in EM, the fields transform well under the Lorentz group too.  Hence, by the philosophy of GR, the metric tensor field has to be regarded as more physical than the Christoffel symbols even though everyone, and Einstein too, calls the metric the « gravitational potential » and the Christoffel symbols the « gravitational field.»  This suggested analogy just shouldn't be taken too seriously, and in fact, Einstein himself constantly oscillates between this terminology and the seemingly contradictory calling the metric tensor field « the gravitational field,» which, at least to me, suggests he didn't think the distinction was that important.

And there is another: in EM we can only measure differences in potentials, of course, so that is why we introduce a choice of gauge and gauge transformations.  But (*pace* extreme positivists), we can in principle measure the metric tensor using light rays and clocks and travelling rods, as explained by Weyl and Einstein.  (Of course only because this is an ideal classical world so we can make the masses negligible...).  Einstein's equations are irrelevant!  Just as, in discussion of what a choice of gauge is and what a gauge transformation is in EM, Maxwell's equations were irrelevant! That is, the definition or concept of gauge and gauge transformation make sense, and one can think about their physicality and desirability, even without considering Maxwell's equations.  And following that road, one could first decide, on physical grounds, what the gauge transformations were, and then search for the Law of Nature that was gauge invariant in that sense.

But the Christoffel symbols, although they can obviously be measured in a sense since they can be calculated from the metric, are not physical because they are not covariant.  Too much argument about what « physical » means would be philosophical, but all I want to really insist on is that for GR, if something isn't even covariant then it is not objective and « real », so this destroys the analogy with gauges in EM all by itself.