There is a simple reason why we can consider variations on the whole $A$ rather than the quotient $C=A/G$ and the reason is following: all configurations that are $G$-equivalent have the same value of the action $S$. That's what we mean by the statement that the theory has the symmetry $G$. So the variation of the action $S$ in the directions that are equivalent to the action of a gauge transformation in $G$ vanish automatically, by the gauge invariance of the action! The variation of the action $\delta S$ is therefore a combination of the variations $\delta a_\mu$ only of those kinds that are independent of the directions along $G$.
That's also why the equations of motion that we derive from $\delta S=0$ don't determine the evolution of the fields such as $A_\mu$ unambiguously out of the initial conditions: the equations of motion only constrain $F_{\mu\nu}$ and they always allow us to change $A_\mu$ in the future, by a gauge transformation. This ambiguity arises from the "flat directions of the action".
You could be studying $\delta S =0$ on the quotient $C=A/G$ only but it would be cumbersome and $\delta S$ would be physically and literally the same thing as it is on $A$. It's the very point of introducing degrees of freedom which include one redundant one (because of the gauge symmetry) to simplify the picture. In fact, the equations of motion from $\delta S= 0$ on $A$ are manifestly Lorentz-covariant etc. If you were trying to parameterize the space $C=A/G$ by some fields, you would probably have to impose some Lorentz-breaking or otherwise unnatural conditions, e.g. $A_0=0$, and the whole formalism would lose the manifest Lorentz symmetry even though the actual phenomena, when looked at properly, would still obey the laws of relativity.
So yes, the methods on $A$ and on $C=A/G$ are equivalent, and it's the calculus on $A$ that is the smarter one. If the formalism using $C=A/G$ were more convenient from all points of view, we would never talk about the gauge symmetry because it would be a totally counterproductive concept! Be sure that it is a very useful concept.
I can't make sense out of the second part of the question. When we discuss infinitesimal variations of quantities such as energy, they should be linear combinations of the infinitesimal variations of the fields, like $dU=\vec E\cdot d\vec D$. But your expression is "doubly infinitesimal", it is bilinear in $\delta X$ where $X$ is something, and terms this small can be neglected in the usual infinitesimal calculus in which $\delta a$ is sent to zero because they're of higher order.
The energy (and stress-energy tensor) is gauge-invariant in electrodynamics, too, so its (linear, first-order) variation induced by gauge transformations is equal to zero. Talking about some second-order "variations" seems completely misguided to me.
Also, less seriously, I feel uneasy about your usage of the word "orthogonal". In general, one doesn't have an inner product (needed to determine orthogonality) on the full configuration space and it's really not needed for most questions of this sort. The directions in $A$ away from a slice that may be used as representatives of $C=A/G$ come in two types: those that are pure gauge transformations, in the direction of the $G$ "fibers", and those that aren't. Most of them "aren't" but any combination of those that are and those that aren't "isn't" again and no combination is really "fundamentally different" than others. So it is a bit meaningless to look for "orthogonal" directions to the directions along $G$.
Finally, you ask whether "a" Gauss law is related to the standard Gauss law taught at school but you haven't really explained what you mean by "a" Gauss law. There is only one Gauss' law. It's the equation of motion obtained by varying the action with respect to $A_0$, and it gives us something like ${\rm div}\,\vec D = \rho$. It's always the same law – which may be generalized to more complicated theories than electrodynamics, e.g. Yang-Mills theory. This equation ${\rm div}\,\vec D =\rho$ is interesting because it doesn't contain any time derivatives. So it really doesn't dictate the time evolution of anything: it already constrains the initial state. One may prove that if the equation holds at $t=0$, it will hold at any time: the time-derivative of the Gauss' law may be derived as a spatial derivative of other Maxwell's equations involving $\vec D$.
This non-dynamical = constraint character of the Gauss' law (the fact it doesn't contain time derivative) is related to the fact that this equation of motion is derived from the variation of a field that may be interpreted as a completely redundant one in a particular convention how to fix the gauge symmetry. That's why we can identify it with the statement that the states related by gauge transformations are treated as equivalent states by the theory. This is particularly clear in the quantum theory where we may a priori have states not annihilated by ${\rm div}\,\vec D - \rho$ but only states that are annihilated by this operator, i.e. states that respect the equivalence of the states related by gauge transformations, may be considered physical.
