Theorem. If $G$ is a finite group with $|G|$ not divisible by $3$, then $|G| \equiv c(G) \mod{3}$. $\\\\$ Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is not a multiple of $3$, these dimensions aren't multiples of $3$. Now reduce modulo $3$ and obtain the congruence. Proof, without character theory: $|G|(|G| - c(G))$ is the number of non-commuting ordered pairs of elements of $G$. Since $|G|$ is a nonmultiple of $3$, the congruence may be proved by showing that this set has a number of elements which is a multiple of $3$. Now just let the lift of $\tau$ act on it: If $(x,y)$ is a fixed point, then reading the first coordinate gives $x=y$, which trivially implies $xy=yx$. So the action is fixed-point-free, and we are done.

Theorem. If $G$ is a finite group of odd order, then $|G| \equiv c(G) \mod{8}$. Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is odd, these dimensions are odd. Now reduce modulo $8$ and obtain the congruence. Proof, without character theory: Instead of lifting $S_{3}$ to $Aut(F_{2})$, lift the dihedral group of order $8$, which is generated by the involutions $(x,y) \to (x^{-1},y)$ and $(x,y) \to (y,x)$. It suffices to check that none of the $5$ involutions of this group has a fixed point in the action on the non-commuting pairs of elements of $G$. This is easy to do, and it involves recalling that, since $|G|$ is odd, $t^{2}=1$ implies $t=1$ for $t \in G$.

Theorem. The number of rows in the character table of $G$ which are entirely real-valued is the number of conjugacy classes $C$ of $G$ such that $x \in C$ iff $x^{-1} in C$. Corollary. If $|G|$ is odd, then the only entirely real-valued character of $G$ is the trivial character.

This leads to a strengthening of the character theory argument used above, so that it now proves that $|G| \equiv c(G) \mod{16}$.

Theorem. If $G$ is a finite group with $|G|$ not divisible by $3$, then $|G| \equiv c(G) \mod{3}$.

Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is not a multiple of $3$, these dimensions aren't multiples of $3$. Now reduce modulo $3$ and obtain the congruence.

Proof, without character theory: $|G|(|G| - c(G))$ is the number of non-commuting ordered pairs of elements of $G$. Since $|G|$ is a nonmultiple of $3$, the congruence may be proved by showing that this set has a number of elements which is a multiple of $3$. Now just let the lift of $\tau$ act on it: If $(x,y)$ is a fixed point, then reading the first coordinate gives $x=y$, which trivially implies $xy=yx$. So the action is fixed-point-free, and we are done.

Theorem. If $G$ is a finite group of odd order, then $|G| \equiv c(G) \mod{8}$.

Proof, with character theory: $|G|$ is the sum of the squares of the dimensions of the complex irreducible representations of $G$. The number of these is $c(G)$. Since $|G|$ is odd, these dimensions are odd. Now reduce modulo $8$ and obtain the congruence.

Proof, without character theory: Instead of lifting $S_{3}$ to $Aut(F_{2})$, lift the dihedral group of order $8$, which is generated by the involutions $(x,y) \to (x^{-1},y)$ and $(x,y) \to (y,x)$. It suffices to check that none of the $5$ involutions of this group has a fixed point in the action on the non-commuting pairs of elements of $G$. This is easy to do, and it involves recalling that, since $|G|$ is odd, $t^{2}=1$ implies $t=1$ for $t \in G$.

Theorem. The number of rows in the character table of $G$ which are entirely real-valued is the number of conjugacy classes $C$ of $G$ such that $x \in C$ iff $x^{-1} \in C$.

Corollary. If $|G|$ is odd, then the only entirely real-valued character of $G$ is the trivial character.

This leads to a strengthening of the character theory argument used above, so that it now proves that $|G| \equiv c(G) \mod{16}$.
In fact, $16$ is the highest power of $2$ that works here, since for any prime $p \equiv 3 \mod{8}$, we can let $G$ be a nonabelian group of order $p^{3}$. This gives $|G| - c(G) = p^{3} - (p^{2}+p-1) = (p^{2}-1)(p-1) \equiv 16 \mod{32}$.

The really tantalizing thing here is that $(p^{2}-1)(p-1)$ is the $p$-free part of the order of the general linear group $GL_{2}(\mathbb{Z} / (p))$.
I do not know whether $|G|-c(G)$ is always a multiple of $(p^{2}-1)(p-1)$ when $G$ is a $p$-group (though the theorems whose proofs I outlined above establish it when $p = 2$ or $p = 3$), and I do not know if some analogue of the lifting argument works, possibly with $Aut(F_{2})$ replaced by $Aut(B(2,p))$ or $Aut(B(2,p^{k}))$, where $B(r,n)$ denotes the rank $r$, exponent $n$ Burnside group.

Also see Bjorn Poonen's paper:
Congruences relating the order of the group to the number of conjugacy classes, American Mathematical Monthly, 105(1995), 440-442.