Perhaps the “Russian” one is Star Trek VI, with the Klingon prison on Rura Penthe? I can see that looking a lot like a Soviet gulag.
I’ll second a suggestion to watch TOS first. They are mostly standalone episodes, with no story arcs longer than a two-parter. The later series can get into longer story arcs. Some of the arcs are composed of continuous episodes (such as DS9’s Dominion War), and some are discontinuous and are more recurring plots, such as Worf’s quest to redeem his father’s honor.
It’s also probably important to realize that many of the TOS episodes were inspired by classic literature, poetry, or myth, and in some cases the borrowing is quite overt, such as “Helen of Troy” -> “Elaan of Troius”.
One other thing to consider is the fact that Star Trek is seen as having been somewhat of a social commentary at times. Cf. TOS’s “Let That Be Your Last Battlefield” as an outrageous commentary on race politics, and Enterprise’s Xindi arc as a commentary on the US’s War on Terror.
There were overlaps in the series’ themselves.
In terms of TNG and DS9, I can recall off the top of my head one TNG episode where the Enterprise-D stops at Deep Space 9 and some of the TNG characters interact with some of the DS9 characters. One episode of DS9 has the Enterprise-D docked at the station. In addition, two characters who were originally on TNG as crew of the Enterprise-D transferred to a duty post on DS9 and became DS9 characters - O’Brien and Worf.
DS9 and Voyager are connected in that Voyager’s mission started at DS9, and a contingent of Maquis (a terrorist group seen in TNG but prominient in DS9) become part of the crew due to the situation the characters find themself in.
While this is largely true, I think a Trek newbie, watching the films, should watch II, III, & IV in that order. IV makes no sense unless you’ve seen III, which makes no sense unless you’ve seen II. ST:TMP (the first one), by contrast, can be skipped entirely; it’s hardly ever referenced by anything later, and I’m not convinced that it’s still not retconned out of existence anyway. VI is optional but worth watching; V should be watched only with plenty of popcorn at hand so you can hurl it at the screen. You’ll know when.
Where No Man Has Gone Before - this looks more familiar…except for Shatner. He looks so…thin. Not very Zap Branigan…although his karate chop fighting style at the end of the episode was very Shatner/Brannigan-esque. And that goes double for Mr Scott. So did they ever sell those 3D chess boards? Why is Spock wearing a gold uniform? I thought he was always in blue. I read a while back that the colors have meaning (red means you’re gonna die this episode). I must say, for a 40 year old TV show, the Bluray remasters look pretty damn good. It’s too bad they can’t remaster the 60s cheese (I couldn’t stop laughing at the obviously painted mural for the Delta Vega background), but I’m enjoying it so far. So how long do I have to watch until I get a backstory to this mission? This episode kept shoving it down my throat that Spock’s species doesn’t feel emotion, but that was about it…so how long until McCoy and Uhura join the show? It’s too bad they killed off Elizabeth, she was pretty easy on the eyes too…
Shatner tended to start the seasons pretty fit, then sloooowly gain weight as the season progressed. It’s a cycle. 
It looks like this may be my fourth post in a row, but here goes:
Continuing the social commentary angle, some of the “races” on Star Trek can be seen as taking a social practice seen on Earth and taking it to an extreme:
Ferengi - greed, capitalism
Klingons - formal, gentlemanly honor (notice that the TNG and later Klingons are socially very very similar to Feudal Japan)
Cardassians - totalitarianism (with sham criminal trials and a literary tradition where sacrifice to the State is the highest virtue)
Borg - cultural imperialism (you WILL be assimiliated!)
Vulcans - asceticism, monasticism
Jem’Hadar (and some minor races) - religious fanaticism
Yes, you can buy 3D chess boards.
Remember, this is the second pilot - lots of things changed, including Spock’s uniform color. There is no backstory - forget it and just move on (remember, no story arcs?).
You left out that he’d lose the excess mass around the three-quarter point.
I recall reading of a fan theory that the planet of machines that V’Ger encountered was an encounter with the Borg.
Confirmed that the “Russia” movie I saw was The Undiscovered Country. I saw that film when I was 12. I wanted to see something else (Bugsy, I think?), but a classmate I was crushing on was in the lobby and I saw her go into Star Trek and so I followed her in. All I remember from the film, having not seen any Star Trek aside from pieces of the “whale movie” and some of the animated cartoons, was “the undiscovered country was…Russia?” but I guess I may have been mistaken. I guess it was a planet which resembled Russia?
Anyway, I’m watching Spock’s Brain next. That sounds waaaaay too good/bad to skip over.
And “The Menagerie” was referenced in Futurama as well as South Park.
It was Rura Penthe.
See, that even SOUNDS like Russia.
There are a few episodes with a wrap-around tunic variation of the captain’s shirt. This acted as a gridle.
Generally speaking, in TOS, the colors correspond to the department you work in:
Gold is Command (captain, helmsman, navigator/astrogator, and the like).
Blue is Sciences (science officer, sensor specialists, medical staff, biologists, geologists, and so forth).
Red is Operations (engineering, communications, security, and various other practical roles).
Being the head of a division overrides Command positions, so even if the Science Officer is also the First (or Executive) Officer, he wears a blue uniform. Spock, for example, might have worn gold at some point if he were already First Officer, but had not yet been made the Science Officer. (I’m not saying that’s why he was wearing one, but it’s a plausible retcon if he’s not actually referred to as the Science Officer at that point.)
The fact that Security is under Operations is the source of most of the Ensign Redshirt joke; if the script called for someone to die away from the ship, it was usually a nameless security guy who went along to protect the officers (which he often did by serving as ablative armor). Ensign Redshirt was occasionally an engineering grunt whose job was to stand next to a dangerously unstable device until it blew up, so it wasn’t always the security guy.
Which fried the Captain’s chaps no end.
snerk
Never heard it put that way before, but it’s accurate enough.
Spock’s Brain - I don’t get it. THIS is the worst Star Trek episode? I liked it a lot more than the other two I’ve watched so far. The cheese factor was up to 11, but in the “so bad it’s good” territory. My only complaint - if planet 6 was supposed to be glacier-covered, why did they beam down without jackets? Do those shirts have climate control? Also, does everyone in the universe speak English, even cavemen on a primitive planet?
I’m gonna watch The Menagerie next. Will I miss anything if I FF through the scenes I already saw in The Cage?
Real men don’t need jackets. No climate control. And yes, everybody in the 'verse speaks 'Merkin.