Perl 5, 111 bytes

sub{%r=%d=();map$r{$_*$_%$n}++,1..($n=$_[0]);//,map$d{($_-$'+$n)%$n}++,@/for@/=keys%r;(sort{$a-$b}values%d)[0]}

Try it online!

K (ngn/k), 26 bytes

{&/#'=,/x!r-\:r:?x!i*i:!x}

Try it online!

{ } function with argument x

!x integers from 0 to x-1

i: assign to i

x! mod x

? unique

r: assign to r

-\: subtract from each left

r-\:r matrix of all differences

x! mod x

,/ concatenate the rows of the matrix

= group, returns a dictionary from unique values to lists of occurrence indices

#' length of each value in the dictionary

&/ minimum

APL(NARS), 24 chars

{⌊/+/∘.=⍨,⍵∣∘.-⍨∪⍵∣×⍨⍳⍵}

I see the other APL solution and i find "∘.-⍨" is shorter than "-/¨∘.,⍨"..., test

  {⌊/+/∘.=⍨,⍵∣∘.-⍨∪⍵∣×⍨⍳⍵}¨1..50
1 2 1 1 1 2 2 1 1 2 3 1 3 4 1 1 4 2 5 1 2 6 6 1 2 6 2 2 7 2 8 1 3 8 2 1 9 10 3 1 10 4 11 3 1 12 12 1 8 4 

in the test it seems ok even i not sure... the size of intervall is 2x and not has the 0 (but result until 50 seems ok)...

Uiua, 19 bytes

/↧°⊚⊛♭◿:⊞-.◴◿:°√⇡..

Try it!

/↧°⊚⊛♭◿:⊞-.◴◿:°√⇡..
                °√⇡    # the squared range from 0 to n-1
             ◴◿:   .   # mod n, deduplicated
       ◿:⊞-.       .  # subtraction table, mod n
  °⊚⊛♭                # the count of each value
/↧                     # minimum

The .s and ◿:s feel golfable, but I'm not really sure how.

Japt -g, 22 20 19 bytes

Outputs the nth term in the sequence. Starts struggling when input >900.

õȲuUÃâ ïÍmuU ü mÊÍ

Try it

APL (Dyalog Unicode), 28 24 bytes

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1}

Try it online!

Prefix direct function. Uses ⎕IO←0.

Thanks to Cows quack for 4 bytes!

How:

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1} ⍝ Dfn, argument ⍵

                   ⍳⍵+1 ⍝ Range [0..⍵]
                 ×⍨     ⍝ Squared
               ⍵|       ⍝ Modulo ⍵
              ∪         ⍝ Unique
          ∘.-⍨          ⍝ Pairwise subtraction table
       ∊⍵|              ⍝ Modulo ⍵, flattened
      ⌸                 ⍝ Key; groups indices (in its ⍵) of values (in its ⍺).
   ⊢∘≢                  ⍝ Tally (≢) the indices. This returns the number of occurrences of each element.
 ⌊/                      ⍝ Floor reduction; returns the smallest number.

C (gcc), 202 200 190 188 187 186 bytes

• Saved two twelve fourteen fifteen bytes thanks to ceilingcat.
• Saved a byte.

Q(u,a){int*d,*r,A[u],t,i[a=u],*c=i,k;for(;a--;k||(*c++=a*a%u))for(k=a[A]=0,r=i;r<c;)k+=a*a%u==*r++;for(r=c;i-r--;)for(d=i;d<c;++A[(u+*r-*d++)%u]);for(t=*A;++a<u;t=k&&k<t?k:t)k=A[a];u=t;}

Try it online!

Ruby, 88 bytes

->n{(z=(w=(0..n).map{|x|x*x%n}|[]).product(w).map{|a,b|(a-b)%n}).map{|c|z.count(c)}.min}

Try it online!

Wolfram Language (Mathematica), 64 bytes

Min[Last/@Tally@Mod[Tuples[Union@Mod[Range@#^2,#],2].{1,-1},#]]&

Try it online!

Python 2, 97 bytes

def f(n):r={i*i%n for i in range(n)};r=[(s-t)%n for s in r for t in r];return min(map(r.count,r))

Try it online!

05AB1E, 22 20 15 13 bytes

LnI%êãÆI%D.m¢

-2 bytes thanks to @Mr. Xcoder.

Try it online or verify the first 99 test cases (in about 3 seconds). (NOTE: The Python legacy version is used on TIO instead of the new Elixir rewrite. It's about 10x faster, but requires a trailing ¬ (head) because .m returns a list instead of a single item, which I've added to the footer.)

Explanation:

L       # Create a list in the range [1, (implicit) input]
 n      # Square each
  I%    # And then modulo each with the input
    ê   # Sort and uniquify the result (faster than just uniquify apparently)
 ã      # Create pairs (cartesian product with itself)
  Æ     # Get the differences between each pair
   I%   # And then modulo each with the input
D.m     # Take the least frequent number (numbers in the legacy version)
   ¢    # Take the count it (or all the numbers in the legacy version, which are all the same)
        # (and output it implicitly)

Jelly,  13  10 bytes

-1 thanks to Dennis (forcing dyadic interpretation with a leading ð)
-2 more also thanks to Dennis (since the pairs may be de-duplicated we can avoid an R and a 2)

ðp²%QI%ĠẈṂ

A monadic link accepting a positive integer which yields a non-negative integer.

Try it online! Or see the first 50 terms.

How?

ðp²%QI%ĠẈṂ - Link: integer, n                   e.g. 6
ð          - start a new dyadic chain - i.e. f(Left=n, Right=n)
 p         - Cartesian product of (implicit ranges)  [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6]]
  ²        - square (vectorises)                     [[1,1],[1,4],[1,9],[1,16],[1,25],[1,36],[4,1],[4,4],[4,9],[4,16],[4,25],[4,36],[9,1],[9,4],[9,9],[9,16],[9,25],[9,36],[16,1],[16,4],[16,9],[16,16],[16,25],[16,36],[25,1],[25,4],[25,9],[25,16],[25,25],[25,36],[36,1],[36,4],[36,9],[36,16],[36,25],[36,36]]
   %       - modulo (by Right) (vectorises)          [[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[3,1],[3,4],[3,3],[3,4],[3,1],[3,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[0,1],[0,4],[0,3],[0,4],[0,1],[0,0]]
    Q      - de-duplicate                            [[1,1],[1,4],[1,3],[1,0],[4,1],[4,4],[4,3],[4,0],[3,1],[3,4],[3,3],[3,0],[0,1],[0,4],[0,3],[0,0]]
     I     - incremental differences (vectorises)    [0,3,2,-1,-3,0,-1,-4,-2,1,0,-3,1,4,3,0]
      %    - modulo (by Right) (vectorises)          [0,3,2,5,3,0,5,2,4,1,0,3,1,4,3,0]
       Ġ   - group indices by value                  [[1,6,11,16],[10,13],[3,8],[2,5,12,15],[9,14],[4,7]]
        Ẉ  - length of each                          [3,2,2,4,2,2]
         Ṃ - minimum                                 2

MATL, 14 bytes

:UG\u&-G\8#uX<

Try it online! Or verify the first 30 values.

Explanation

:      % Implicit input. Range
U      % Square, element-wise
G      % Push input again
\      % Modulo, element-wise
u      % Unique elements
&-     % Table of pair-wise differences
G      % Push input
\      % Modulo, element-wise
8#u    % Number of occurrences of each element
X<     % Minimum. Implicit display