Consider that the question does not concern the origin of the ideas of equivalence relation and equivalence class. It exactly concerns the origin of the terms "equivalence relation" and "equivalence class". It seems that the terms weren't in use at least until 1903 where Russell writes:
Peano has defined a process which he calls definition by abstraction,
of which, as he shows, frequent use is made in Mathematics. This
process is as follows: when there is any relation which is transitive,
symmetrical and (within its field) reflexive, then, if this relation
holds between u and v, we define a new entity Ø (u), which is to be
identical with Ø (v).Relations which possess these properties are an important kind, and
it is worthwhile to note that similarity is one of this kind of
relations.
UPDATE: Thanks to the suggestions given in the comments and a very informative answer of Francois Ziegler, suddenly the following piece from Russell's Introduction to Mathematical Philosophy came into a new light:
The question “what is a number?” is one which has been often asked,
but has only been correctly answered in our own time. The answer was
given by Frege in 1884, in his Grundlagen der Arithmetik. Although his
book is quite short, not difficult, and of the very highest
importance, it attracted almost no attention, and the definition of
number which it contains remained practically unknown until it was
rediscovered by the present author in 1901.
So, perhaps that was Frege himself who used the terms! Although, I couldn't find anything in Frege's writings yet. But now, considering Eugen Netto's paper (see Francois' update below) a very more important question now is: Is he indeed Russell who should be credited with rediscovering Frege in 1901?!
PS. I am well aware that asking a new question inside another question is not a good idea. However, up until this post I had the feeling that apart from the origin of the terms I know "everything" about the history of the notions of equivalence relation and equivalence class (part of which has been published here). But, this new information caught me by surprise, and I could not help myself to add the new question. You may just ignore it.
Best Answer
Von Neumann uses "equivalence class" in Zur Prüferschen Theorie der idealen Zahlen, Acta Sci. Math. (Szeged) 2 (1926) 193-227, p. 197 (viewable after free registration):
This seems like an early example, in that he sees fit to add here the footnote: "We define the ideal number as the corresponding set of fundamental sequences, itself; naturally one could also regard it as an ideal element attached to this set."
I note also that Hasse's book Höhere Algebra (where Henry Cohn found the earliest occurrence of "equivalence relation" so far) appears to have a 1926 edition too.
Update 1: One might also quote a paper by Eugen Netto, Über die arithmetisch-algebraischen Tendenzen Leopold Kronecker's, in: Mathematical Papers read at the International Mathematical Congress (Chicago, 1893), Macmillan 1896, pp. 243-252, who writes:
Update 2: Finally(?) one should probably also quote Vol. 2 of Weber's Lehrbuch der Algebra (1896). Literally he uses neither "equivalence relation" nor "equivalence class", but see how close he gets in §152 "Aequivalenz":
Same for Dedekind's Ueber die Theorie der algebraischen Zahlen (1879), §175:
(Of course, calling class a family of objects related by some equivalence is a custom that can be traced to much older work — cf. Dirichlet [1863, p. 172] or Eisenstein [1847, p. 118] or Gauss [1801, §223].)