The reason it gets murky is that the kind of use of which Dedekind cuts are prototypical became characteristic only after the arithmetization of analysis at the end of 19th century. Dedekind did not publish his 1858 work until 1872, by which time Cantor already started publishing his papers on point sets with similar ideas, including his own construction of real numbers as classes of rational sequences. This was a key difference between them and their closest precursor, Bolzano, who could not prove existence of say least upper bounds "rigorosly" because he lacked such constructions. We can bootstrap some prior uses into this but then what qualifies as "bona fide" becomes a judgement call. This is not uncommon, modern concepts have their precise meanings only in the modern context, when we try to apply them before that we are stretching it. But of course the modern context does not emerge out of nothing. Paradoxically, in history there are often no "firsts".
The tradition of geometric loci predates Euclid. A locus is a figure singled out by a property ("symptom", as Apollonius called it), e.g. the locus from which exactly two normals to a parabola can be drawn, considered by Apollonius. Aristheus (c.350 BC) wrote a book Plane Loci, not extant but mentioned by Pappus, which served as a stepping stone to the work of Euclid and Apollonius on conic sections. We now identify loci with "sets of points", but this is not exactly how Greeks saw it, lines and planes were not dissociated into points then. Descartes brought these ideas closer to modern use in La Geometrie (1637), when he coordinatized the plane and identified loci with "zero sets" of polynomials, but even he does not treat them as "sets of coordinate pairs" as we do today.
First Euler (1750, unpublished until 1849) and then more explicitly Gauss in Disquisitiones Arithmeticae (1798, published 1801) introduced congruence classes (Euler called them residues and preferred to think of them as remainders), and algebraic manipulations with them, the modular arithmetic, see Is Gauss the first who introduced congruences? These are perhaps closer in spirit to Dedekind cuts, indeed the whole idea of arithmetizing analysis was in part motivated by importing "Gauss's rigor" from arithmetic.
The tradition Boole was following can be traced at least as far back as Leibniz, and with some charity to Raymundus Lullius or even Aristotle. This is complicated by the conflation of intensions with extensions which persisted until the early 20th century, so in the early sources what is represented are more concepts than classes or sets they define. In any case, they were treated as "objects" with extensional connotation due to representation by circles or other figures in diagrams, what we now call "Venn diagrams". The use of diagrams was popularized by Euler, but as Baron writes in A Note on the Historical Development of Logic Diagrams:"Despite Euler's stature as a mathematician he apparently made no attempt to develop these relations algebraically. Nonetheless, through him, knowledge of the diagrams became widespread and they had some considerable influence in the nineteenth century". Boole was one of the first to start thinking of what the circles represent as "classes" (extensions) rather than concepts, Venn, who gave the most comprehensive account of the diagrams and their manipulation, followed him. But the conflation is still present even in Russell and Zermelo, the purely extensional use is clearly articulated only in Hausdorff's Grundzuge der Mengenlehre (1914), see How did mathematicians notate the empty set before $\varnothing$?
