Relationship between symmetry and computational intractability?
This isn't exactly the "same" relationship between symmetry and hardness, but there is a close relationship between the symmetries of a Boolean function and its circuit complexity.  See:


  Babai, L., Beals, R., and Takácsi-Nagy, P.  Symmetry and complexity, STOC 1992.


Here's what they show. Let $G_{i} \leq S_{i}$ be a sequence of permutation groups. Let $s(G_{i})$ denote the number of orbits of $G_{i}$ in its induced action on $\{0,1\}^{i}$ (by permutation of the coordinates).  Let $\mathcal{F}(G)$ denote the class of languages $L$ such that $L \cap \{0,1\}^{n}$ is invariant under $G_{n}$.  Then all languages in $\mathcal{F}(G)$ have circuits of size at most $poly(s(G))$ and depth at most $poly(\log(s(G))$, and this is essentially tight.



In the opposite direction, several $NP$ problems whose witness sets have lots of symmetries end up being in $coAM$ (like $GI$), and so are not $NP$-complete unless $PH$ collapses.  In fact, the following paper shows that $NP$ problems whose witness sets have lots of symmetries are low for $PP$:


  Arvind, V., Vinodchandran, N. V. The counting complexity of group-definable languages. Theoret. Comput. Sci. 242 (2000), no. 1-2, 199--218.


(Note: whether or not "low for $PP$" indicates "unlikely to be $NP$-complete" is a little up in the air, as far as I know. Toda and Ogiwara showed that $PP^{PH} \subseteq BP \cdot PP$.  So under the "derandomization" assumption $BP \cdot PP = PP$, $NP$ is in fact low for $PP$, so being low for $PP$ is no obstacle to being $NP$-complete.  On the other hand, there is an oracle due to Beigel relative to which $NP$ is not low for $PP$.)



In a similar vein as the above, if every polynomial-time decidable equivalence relation has a polynomial-time complete invariant (function $f$ such that $f(x) = f(y)$ iff $x \sim y$), then any $NP$ problem whose witnesses have lots of symmetries reduces to the hidden subgroup problem for the automorphism group of its witnesses.  Admittedly, the hypothesis here is rather unlikely to hold, but it does give some connection between symmetry and quantum complexity.



Finally, the Mulmuley-Sohoni Geomectric Complexity Theory program is essentially about using symmetry to prove hardness, though the symmetry-hardness connection there is more subtle and less direct.