After their adventure on Skaro (thus continuing the interconnectedness of these stories87) , the Doctor and his companions arrive via Time Ring on Nerva -- only it's a lot earlier than when they left. The Nerva of this time period ("thousands of years before" the solar flares, the Doctor tells Harry -- but maybe he actually means thousands of years before the events of The Ark in Space) has been severely afflicted by a plague which has killed virtually everyone on board -- there are only four people left alive. Everyone else has been struck down by this strangely familiar-looking disease (although, to be fair, it has been nine years since The Moonbase, so maybe it wasn't that familiar to the audience), while large silver snake bugs slither around. Oh, and there's clearly a slimy traitor on board who's contacting the Cybermen. It's a reasonable set-up, but the problem is that Kellman is such an obvious traitor that the question is about how he'll be stopped, rather than who the traitor is. The new redesigned Cybermats also seem awkward and ungainly -- no one has seen these huge things moving around on Nerva? But no, they're leaping on people and biting them in the neck, and Sarah is attacked in part one's cliffhanger.88
Nerva is where it is, by the way, because fifty years earlier a large asteroid showed up near Jupiter ("So you mean there are now thirteen [satellites of Jupiter]?" the Doctor infamously asks89), so Nerva is there to warn passing ships of the new astronavigational hazard. The asteroid is all that's left of Voga, the planet of gold that was instrumental in defeating the Cybermen "centuries ago" at the end of the Cyber War. The Vogans have managed to survive in the interim, though. The problem with the Vogans is that the audience isn't given much background or reason to care about them before they start engaging in a sort of civil war, and so it just looks more like a bit of incident along the way for Harry and Sarah to get out of than anything else. (Sarah, by the way, has been cured of the Cyber-infection by passing through a transmat -- pity no one else thought of that.) And while the Vogan sets and location footage work well together to create the world of Voga (and remember that fancy figure-eight symbol -- it'll come up again in season 14), the Vogans themselves leave something to be desired. The hero masks are reasonably good, but all the extras/stuntmen are wearing less-developed masks with visible gaps between the mask and the actors' own eyes that significantly ruin the effect.
But the main concern with these first two episodes of Revenge of the Cybermen is that it doesn't feel like anything really happens. There's some Vogan politics and such to try and keep things moving, but any real drama feels like it's being delayed with the appearance of the Cybermen (the Cybermen! We haven't seen them for seven years!), who don't really show up (other than a brief scene here and there) until the end of part two, when they shoot down the two remaining crewmen -- and the Doctor! Everything prior feels like it's building to this point. Let's hope the pay-off is worth it.
87 Even if, oddly, Sarah makes reference to "these past few weeks", which suggests that either they were on Skaro for a hell of a lot longer than we thought, or there are indeed somehow unseen adventures in this arc of stories.
88 Not exactly relevant to this story, but it's worth noting that William Hartnell died between parts one and two, on 23 April 1975.
89 Stephen Cole tries to explain away this line by basing the penultimate Eighth Doctor Adventure To the Slaughter on it, if you feel so inclined (in which a bunch of Jovian moons are destroyed in the name of cosmic feng shui), but it's worth noting that this number was accurate when Revenge of the Cybermen was written -- though not by the time of filming and subsequent broadcast, as a thirteenth moon, Leda, was discovered in September 1974.