Lessee, I consider myself a fan and by my estimate I may have missed two thirds of the episodes in the franchise (not counting the cartoon and books).
TNG was a bit awkward for the first couple seasons until they found their feet. DS9 was the same way. I’d say, along with whatever episodes from the first two seasons you get recommended (maybe watch the pilot, Encounter at Farpoint, just because it gets a callback in the series finale) you’d probably do well to start with the season 2 finale, “The Neutral Zone”. It’s got a sort of weird premise (three 21st century humans in cryo thawed out and having to adjust to the 24th century), but it does a rather good job setting up two of the show’s most important villains.
Don’t worry about the shows overlapping, they don’t really cross over much at all. The DS9 premiere kinda runs paralel to the TNG 7th season premiere, but for the most part, they’re both just there. Enterprise is docked at DS9 with her crew doing their thing, and the DS9 crew is aboard the station doing their own thing, with a few characters talking to each other. The first episode of Voyager similarly starts at DS9, but for reasons that pretty much make up the entire basis of the show, the Voyager and DS9 crews aren’t going to see each other for a long while.
If you get burnt out on TOS for some reason, watch Star Trek II and Star Trek VI and move on to TNG. Star Trek II is a “sequel” to a TOS episode, but is a very solid movie on its own (really, the episode it was a sequel to was goofy as hell, though if you skip it, you miss out on McCoy being a cool-headed badass when someone puts a knife to his neck.) I think Star Trek VI is the one you’re thinking of when you say “They go to Russia”, since it’s very very heavy on the late-Cold War overtones. No Russians in any of the movies though unless you count Chekov (he’s Ukrainian).
DS9, watch the pilot episode, then skip to the season 2 finale, “The Jem’Ha’Dar”, which introduces the main villains for that show (and has an epic moment of one of the comic-relief aliens successfully calling bullshit on the holier-than-thou attitude that Starfleet tends to have towards others).
DS9 is sort of a deconstruction of a lot of the way we see the humans in Star Trek, partially because it takes place outside the Federation, and so we get to hear what a lot of the aliens actually think of the guys preaching peace from the bridges of the huge heavily armed starships. At least one episode is about 14 times more entertaining if you have seen a specific TOS episode.
Voyager I never watched much of. I’d say find out which episodes center on the “Captain Proton” holodeck adventures and just watch those. (Two of the characters enjoy role-playing as Flash Gordon knock-offs in the holodeck. Many other characters get involved and pretty much can’t wrap their heads around why someone would enjoy such campy stories. They even shift to grainy black and white for those parts.) Enterprise similarly I didn’t catch a lot of for various reasons.
But really, don’t feel pressured to watch the whole franchise RIGHT NOW OMG, just enjoy it.
Oh, as far as stuff in Star Trek that “never happened”, “Spock’s Brain” gets a lot of shit for being, well, a ridiculous episode (Spock’s brain gets stolen. McCoy installs a remote control in his body so he can walk him around like a remote controlled puppet. It goes downhill from there). Also, I’m told that the Star Trek writers all have a strict unwritten rule not to ever reference anything that happened in Star Trek V: The Final Voyage. There are one or two great moments (both involving Spock, naturally), but otherwise the entire movie is more or less a wash.
