Actually, I think that the phenomenon here is that GI in some sense has too much structure. It is in some ways the group-theoretic nature of its witnesses which leads to the $\mathsf{coAM}$ algorithm for GI and is one of the pieces of technical evidence why people believe GI is not $\mathsf{NP}$-complete. My thinking here is that there is so much structure that the problem is "too rigid" to encode arbitrary $\mathsf{NP}$ problems.
Another way to capture this is the fact that the counting and decision versions of GI are equivalent, whereas for all known $\mathsf{NP}$-complete problems this is not the case unless the polynomial hierarchy collapses. This can also be viewed as capturing some aspect of structure/redundancy: for unstructured, general problems, counting solutions seems to be much harder than telling if one exists, whereas the extensive structure of GI allows one to show that counting and decision are equivalent.
(On the other hand, group isomorphism seems even more structured than GI, yet no counting-to-decision reduction is known for group iso. Perhaps this says that GI is in sort of a "just right" level of structure - too structured to be NP-complete, but unstructured enough to allow a counting-to-decision reduction.)