I feel remiss in not touching on the Tribble episodes... With the exception of the Animated series episode, I had seen them before. They are that rarity in Star Trek - funny episodes that are actually funny. There are a couple of others. The Magnificent Ferengi is great (possibly just because Iggy Pop is in it). But these work really well.
I gave up on Star Trek much earlier than @Lorcan_Nagle I think, but somehow I saw Trials and Tribble-ations. I remember that there was a big fuss made over the way that the DS9 characters were integrated into existing footage, a la Forrest Gump. I am not sure how I saw it. But yes, Worf is brilliant in it.
The two Department of Temporal Investigations Agents were subsequently spun off into their own series of novels, which I have enjoyed. Edit: Basically it is the story of two obsessive compulsive time detectives in the Star Trek universe. What's not to like?
In answer to the other point, I am happy with any of the suggestions. I am conscious that we went with a crowd pleasing thing...and prompted very little discussion at all. So something a bit more challenging or contentious might be a good idea. I know that Alx suggested Tapestry a while back,