I think we're pretty much in agreement on "Rejoined" -- I agree that it's all the stronger for not making a Very Special Issue of the relationship being between two women. I don't really see it as a sci-fi cheat myself, but can understand why some people do, especially coupled with that TNG episode that really was heavy-handed sci-fi allegory and would have been fresher in people's memories at the time this aired.

As for whether producers could have done better at the time ... maybe this is where your non-Trekkie status gives you perspective, or realistically lower expectations of TV producers. In the Trekkie milieu of the '90s, we were used to Trek powers-that-be patting themselves on the back for the franchise's vision of an enlightened future, which fed this naive expectation they'd blaze new trails rather than lag behind.