On partitioning a collection into equivalence classes
See the paper

Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons",
Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/978-3-319-21840-3_36

It is exactly about the problem you ask, finding the equivalence classes of an equivalence relation by querying the equivalences of pairs of elements. For an input with $n$ elements and $c$ equivalence classes, the naive algorithm you describe will take time $O(nc)$, but they give a more precise bound for this same algorithm in terms of the sizes of its equivalence classes (Theorem 3) and similarly analyze another algorithm for the same problem that works better when the equivalence classes have unevenly distributed sizes (Theorem 4).