I will mostly talk about the classical physics as this is complicated enough already (I might mention something about quantum stuff at the end). So, let us first get all the relevant terms straight, so that we avoid any further confusion. In particular, we need to be precise about what we mean by invariance because already two different notions have been thrown into one bag.
A symmetry group of a physical system is a group of transformations that leave the system invariant. E.g. the electric field of a point charge is invariant under rotations w.r.t. to that point. In other words, we want the group to act trivially. But that means that this immediatelly rules out any equations that carries tensorial indices (i.e. transforms in a non-trivial representation of the rotation group). For these equations, if you perform a rotation, the equation will change. Of course, it will change in an easily describable manner and a different observer will agree. But the difference is crucial. E.g. in classsical quantum mechanics we require the equations to be scalar always (which is reflected in the fact that Hamiltonian transforms trivially under the symmetry group).
Carrying a group action is a broader term that includes tensorial equations we have left out in the previous bullet point. We only require that equations or states are being acted upon by a group. Note that the group action need not have any relation to the symmetry. E.g. take the point charge and translate it. This will certainly produce a different system (at least if there is some background so that we can actually distinguish points).
A gauge group of a system is a set of transformations that leave the states invariant. What this means is that the actual states of the system are equivalence classes of orbits of the gauge group. Explicitly, consider the equation ${{\rm d} \over {\rm d} x} f(x) = 0$. This has a solution $g(x) \equiv C$ for any $C$. But if we posit that the gauge group of the equation consists of the transformations $f(x) \mapsto f(x) + a$ then we identify all the constant solutions and are left with a single equivalence class of them -- this will be the physical state. This is what gauge groups do in general: they allow us to treat equivalence classes in terms of their constituents. Obviously, gauge groups are completely redundant. The reason people work with gauge groups in the first place is that the description of the system may simplify after introduction of these additional parameters that "see" into the equivalence class. Of course historical process went backwards: since gauge-theoretical formulation is simpler, this is whan people discovered first and they only noticed the presence of the gauge groups afterwards.
Now, having said this, let's look at the electromagnetism (first in the flat space). What symmetries are the Maxwell equations invariant under? One would like to say under Lorentz group but this actually not the case. Let's look at this more closely. As alluded to previously the equation
$$\partial_{\mu} F^{\mu \nu} = J^{\nu}$$
can't really be invariant since it carries a vector index. It transforms in the four-vector representation of the Lorentz group, yes -- but it is certainly not invariant. Contrast this with the Minkowski space-time itself which is left invariant by the Lorentz group.
We also have ${\rm d} F = 0$ and therefore (in a contractible space-time) also $F = {\rm d} A$ which is obviously invariant w.r.t. to $A \mapsto A + {\rm d} \chi$. In terms of the above discussion the equivalence class $A + {\rm d} \Omega^0({\mathbb R}^{1,3})$ is the physical state and the gauge transformation lets us distinguish between its constituents
Let's move to a curved spacetime now. Then we have
$$\nabla_{\mu} F^{\mu \nu} = J^{\nu}$$
Again, this is not invariant under ${\rm Diff}(M)$. But it transforms under an action of ${\rm Diff}(M)$. The only thing in sight that is invariant under ${\rm Diff}(M)$ is $M$ itself (by definition).
In the very same way, GR is not invariant under ${\rm Diff}(M)$ but only transforms under a certain action of it (different than EM though, since GR equations carry two indices). Also, ${\rm Diff}(M)$ can't possibly be a gauge group of any of these systems since it would imply that almost all possible field configurations get cramped to a single equivalence class possibly indexed by some topological invariant which can't be changed by a diffeomorphism. In other words, theory with ${\rm Diff}(M)$ as a gauge group would need to be purely topological with no local degrees of freedom.
