IIRC the first episode we see them in is TNG's Q Who when Q throws the Enterprise into another quadrant to prove to Picard that they aren't ready for what's out there, but I don't recall whether they said "Resistance is Futile" in that episode.
To emphasize, I'm looking for the first occurrence of "Resistance is Futile" in episode airing order (in any of the Star Trek shows/films), not timeline order. So we don't have to worry about that First Contact storyline. :-)