First of all, Sean Carroll is a relativist so his treatment of the diffeomorphism symmetry as a gauge symmetry should be applauded because it's the standard modern view preferred by particle physicists – its origin is linked to names such as Steven Weinberg, it is promoted by physicists like Nima Arkani-Hamed, and naturally incorporated in string theory so seen as "obvious" by all string theorists. In this sense, Carroll throws away the obsolete "culture" of the relativists. There are some other "relativists" who irrationally whine that it shouldn't be allowed to call the metric tensor "just another gauge field" and the diffeomorphism group as "just another gauge symmetry" even though this is exactly what these concepts are.
Second of all, a symmetry expressed by a Lie algebra can't be "discrete", by definition: it is continuous. Lie groups are continuous groups; it is their definition. And only continuous groups are able to make whole polarizations of particles unphysical. It's plausible that a popular book replaces the continuous groups by discrete ones that are easier to imagine by the laymen but this server is not supposed to be "popular" in this sense.
Third, when you say that if $U$ is unitary, the generator has to be Hermitian and traceless, is partly wrong. Unitarity of $U$ means the hermiticity of the generators $T^a$ but the tracelessness of these generators is a different condition, namely the property that $U$ is "special" (having the determinant equal to one). The tracelessness is what reduces $U(N)$ to $SU(N)$, unitary to special unitary.
Fourth, and it is related to the second point above, "charge conjugation" isn't any gauge principle of electromagnetism in any way. Electromagnetism is based on the continuous $U(1)$ gauge group. This group has an outer automorphism – a group of automorphisms is ${\mathbb Z}_2$ – but we're never putting these elements of the discrete group into an exponent.
Fifth, similarly, QCD isn't based on the discrete symmetry of permutations of the colors but on the continuous $SU(3)$ group of special unitary transformations of the 3-dimensional space of colors. Because none of the things you wrote about the non-gravitational case was quite right, it shouldn't be surprising that you have to encounter lots of apparent contradictions in the case of gravity as well because gravity is indeed more difficult in some sense.
Sixth, $SO(3,1)$ isn't related to the diffeomorphism in any direct way. It is surely not the same thing. This group is the Lorentz group and in the GR, you may choose a formalism based on tetrads/vielbeins/vierbeins where it becomes a local symmetry because the orientation of the tetrad may be rotated by a Lorentz transformation independently at each point of the space. But this is just an extra gauge symmetry that one must add if he works with tetrads – it's a symmetry that exists on top of the diffeomorphism symmetry and this symmetry is different and "non-local" because it changes the spacetime coordinates of objects or fields while all the Yang-Mills symmetries above and even the local Lorentz group at the beginning of this paragraph are acting locally, inside the field space associated with a fixed point of the spacetime. (The fact that diffeomorphisms in no way "boil down" to the local Lorentz group is a rudimentary insight that is misunderstood by all the people who talk about the "graviweak unification" and similar physically flawed projects.) I will not use with tetrads in the next paragraph so the gauge symmetry will be just diffeomorphisms and there won't be any local Lorentz group as a part of the gauge symmetry.
The diffeomorphism symmetry is locally generated by the translations, not Lorentz transformations, and the parameters of these 4-translations depend on the position in the 4-dimensional spacetime. This is how a general infinitesimal diffeomorphism may be written down. If there were no gauge symmetries, $g_{\mu\nu}$ would have 10 off-shell degrees of freedom, like 10 scalar fields. However, each generator makes two polarizations unphysical, just like in the case of QED or QCD above (where the 4 polarizations of a vector were reduced down to 2; in QCD, all these numbers were multiplied by 8, the dimension of the adjoint representation of the gauge group, $SU(3)$ etc.). Because the general translation per point has 4 parameters, one removes $2\times 4 = 8$ polarizations and he is left with $10-8=2$ physical polarizations of the gravitational wave (or graviton). The usual bases chosen in this 2-dimensional physical space is a right-handed circular plus left-handed circular polarized wave; or the "linear" polarizations that stretch and shrink the space in the horizontal/vertical direction plus the wave doing the same in directions rotated by 45 degrees:

This counting was actually a bit cheating but it does work in the general dimension. To do the counting properly and controllably, one has to distinguish constraints from dynamical equations and see how many of the modes of a plane wave (gravitational wave) are affected by a diffeomorphism. In the general dimension of $d$, it may be seen that the tensor $\Delta g_{\mu\nu}$ may be described, after making the right diffeomorphism, by $h_{ij}$ in $d-2$ dimensions and moreover the trace $h_{ii}$ may be set to zero. This gives us $(d-2)(d-1)/2-1$ physical polarizations of the graviton. In $d=4$, this yields 2 physical polarizations of the graviton. A gravitational wave moving in the 3rd direction is described by $h_{11}=-h_{22}$ and $h_{12}=h_{21}$ while other components of $h_{\mu\nu}$ may be either made to vanish by a gauge transformation (diffeomorphism), or they're required to vanish by the equations of motion or constraints linked to the same diffeomorphism. Morally speaking, it is true that we eliminate two groups of 4 degrees of freedom, as I indicated in the sloppy calculation that happened to lead to the right result. Note that
$$\frac{d(d+1)}2 -2d = \frac{(d-2)(d-1)}2-1 $$
I have to emphasize that these is a standard counting of the "linearized gravity" and it's the same procedure to count as the counting of physical polarizations after the diffeomorphism "gauge symmetry" – just the language involving "gauge symmetries" is more particle-physics-oriented.