1) One can say something about the $k$-neighbourhoods of a vertex $v$ (i.e. sets of vertices at distance $k$ from $v$). For $v=()$, the identity element of $S_n$, each $k$-neighbourhood is a union of conjugacy classes of $S_n$.

E.g. for $k=1$ you get $n \choose 2$ vertices, corresponding to involutions of type $2^1$, a.k.a. transpositions $(ab)$, and there are no edges between them. That is, there are no triangles in your graph. By the way this immediately tells you that $K_{888}$ for $G_4$ is very far off.

For $k=2$ you get two types of vertices, namely, the ones corresponding to involutions of type $2^2$, i.e. $(ab)(cd)$, and the ones corresponding to $3$-cycles $(abc)$. This will tell you that for any two vertices at distance 2 there is unique 4-cycle which contains them.
Indeed, you can get $(ab)(cd)$ using two transpositions either as $(ab)\cdot (cd)$ or as $(cd)\cdot (ab)$, and you can get $(abc)$ either as $(ac)\cdot (bc)$ or as $(bc)\cdot (ab)$.

2) Another interesting and sometimes useful fact is that the eigenvalues of the adjacency matrix $A$ of $G_n$ can be computed from the values of the irreducible characters of $S_n$; namely, $A$ can be viewed as an element $\sum\limits_{\pi \text{ a transposition}}\pi$ in the center of the group algebra $\mathbb{C}[S_n]$, and the center is generated by such conjugacy class sums; this allows you to simultaneously diagnonalise them, etc.

1more comment