At the request of Gerry Myerson, here is what I understand.
As $n^2=1$ modulo $n^2-1$, the multiplication by $n$ graph on $m=n^2-1$ vertices as defined in the question is formed
1) First, of isolated points which satisfy $nx=x$, or equivalently $(n+1)|x$, of which there are $n-1$. These are the $n-1$ initial point of each "cusps" (a "cusp" is a group of $n+1$ consecutive points on the circle starting with a point congruent to 0 modulo $n+1$).
2) Second, of bi-directional edges relating a pair of points. Now, if $x=y+k(n+1)$ with $0\leq y\leq n$, then $nx=ny+k+kn=ny+k(n+1)=-y+(k+y)(n+1)$ so each point in the $n+1$ terms are linked to a different group.
This entirely explains the nice display when $m=n^2-1$. If $m<n^2-1$, then $(n-1)(n+1)>m$, so there can be no periodicity of the form above.
Now, how about the assertion that when $m$ is large with respect to $n$, we do see $n-1$ "cusps"? The slopes of two consecutive edges (corresponding to $nx$ and $n(x+1)$) are increasing. Visually, if you incrementally increase slopes of lines, this draws the convex envelope of a cusp (people who know more than me about geometry, that is to say people who know anything at all, will tell us the equation of the cusp drawn in this way). Whence the cusps. When will the cusps be dark (almost vertical slope)? When the edges are close to diameters. And when will that be? When $nx$ is close to $x+m/2$. If that is the case, then $n(x+m/(n-1))$ will also be close to $x+m/(n-1)+m/2$. So we see $n-1$ maximally dark cusps (and likewise one can count the relatively darker cusps by cutting the circle in 3, 4 etc. and translate in terms of congruences).
Putting everything together, if $m$ is large, we see $n-1$ dark cusps, if $m=(n-1)(n+1)$ we see $n-1$ grouping shuffled by multiplication by $n$ and this periodicity can not occurred if $m<(n-1)(n+1)$. So yes, $n^2-1$ is the first instance in which the ultimate pattern unambiguously appear.