I've just watched Marco Polo as part of my Who marathon, thanks entirely to Loose Cannon, who have provided a superb recon. I should just note that there are some fans who will insist that a story cannot be judged based on its soundtrack alone, or even a recon I dont agree, since the heavy dependence on dialogue of Doctor Who at the time easily allows most of the missing stories to transfer fairly easily to audio, especially with narration or captions to cover the action sequences. However, if anyone out there does stridently insist that I cant judge an incomplete story without having seen it as first broadcast, then read no further and wait until I get to The Keys of Marinus.
Anyway, Marco Polo is an interesting story for several reasons. Firstly of course, it is the earliest missing story and is completely missing (not even clips survive), which have given it a near-legendary status. This is helped by the fact that the soundtrack has not yet been released on CD and is (at least my experience) harder to get bootleg copies of than the other missing episodes. Secondly, it is the first historical, and also the longest. Finally, as I have noted previously, the relationship between the TARDIS crew members has now been established by the previous three stories, and this allows individual supporting characters to really shine in Doctor Who for the first time.
Marco Polo has four major guest characters of note: Marco Polo, Tegana, Ping-Cho, and Kublai Khan. Polo himself is a superb character, essential noble and seemingly keen to gain the friendship of the travelers, for whom he develops respect, but unable to fully do this due to his theft of the TARDIS. Desperate to return home to Venice, he insists on presenting the ship to the Khan to try and negotiate his freedom from service, but in doing so he denies it to the Doctor and his friends. His resolve prevents him from relenting and indeed he does present the TARDIS to the Khan, but he struggles with his conscience throughout, knowing that he has acted unjustly. The problem lies partly with the fact that he doesnt understand the TARDIS he believes it is a caravan that flies, but doesnt understand just how advanced it is, assuming that the Doctor can build a new one and offering to grant the travelers safe passage home. It is this plot device that keeps the Doctor and friends on Cathay, since Polo manages to separate them from the TARDIS as effectively as any lost fluid link, and it makes their troubles greater in many ways  unable to convey their urgency to Polo, they make frequent attempts to regain the ship, refusing to give Polo, who is otherwise well-disposed towards them, their word that they will not make further such attempts. This places them in a quandary when it becomes clear that Tegana is not all he seems, since Polo cannot fully trust them and is more inclined to believe TeganaÂs accounts whenever they accuse him of mischief. Ultimately though, Polo returns the TARDIS key to the Doctor in the court of Kublai Khan, during the confusion after Teganas defeat. Ian has by this point tried to tell him the whole truth about the TARDIS, to which Polo replies that he if believed Ian he would give them the key back, realizing that the travelers could find no other way home. After the travelers are instrumental in Teganas defeat, Polo finally realises that Ian was telling the truth, and gives the Doctor the key beneath the Khans very nose; in a story concerned with the theme of going home (the Doctor and his companions, Polo, and Ping-Cho are all motivated by a desire to do so) Polo realises that, even if the Khan will not let him return home to Venice, then at least the travelers can go home.
Tegana is the first real single villain in Doctor Who the Daleks are a race of monsters, and Kal and Zas struggle for leadership and survival is hardly the same as the sort of scheming villain that will recur in Doctor Who. The Warlord Tegana is an excellent villain, cold and ruthless, but cunning enough to hide his true intent (to kill the Khan in the name of his own Lord, Noghai) from Polo at least. Even before we learn of this, he is established as a threat when the travelers first encounter Polos party, it is Tegana that they meet and his is keen to kill these supposed evil spirits. Polo saves them, but Tegana threatens them at every turn, responsible as he is for all the various ills that befall PoloÂs caravan. Derren Nesbitt brings great presence to Tegana, who is a softly spoken, commanding character; he easily convinces Polo that he, and not the travelers, is lying when they try to accuse him of villainy on several occasions, and he convinces Polo to let him ride back for Ian and Ping-Cho, both of whom he intends to kill, despite the TARDIS crews and Ping-Chos warnings that he is up to something. Tegana is also quick to improvise to cover his actions, casually explaining that he was delayed at the oasis by bandits and easily fending off any suspicions. He is ruthless too, prepared to kill even Ping-Cho, since she is in his way. He also unhesitatingly dispatches his allies, including Acomat, when the need to maintain secrecy arises. Presumably he is also very dedicated, given that he could not reasonably expect to stay alive for long after completing his mission. His penultimate encounter with Polo, when he casually and easily ruins Polos hopes of the Khan letting him return to Venice, shows him swiftly discarding his façade in order to get the Khan alone, at which point he tries his assassination attempt. When Polo out-fights and disarms him, rather than answer to the Khan, he almost definitely commits suicide, impaling himself on a sword a fitting end for one of Doctor Whos earliest villains.
Ping-Chos importance stems mainly from her friendship with Susan, which draws her to aid the travelers, partly due to their sympathy at her plight she is being forced to marry a man old enough to be her grandfather. Like the TARDIS crew and Polo, she is keen to return home, but simply to afford marriage once her husband to be dies, she happily remains in the Khans court. It is interesting to speculate that this is also in part due to the influence of Susans tales of her travels, which might well have encouraged Ping-Cho to experience the thrills on offer at the court of Kublai Khan. The Khan himself is the fourth guest character of particular note, due largely to his relationship with the Doctor. The two old men, one crippled by gout and the other with a bad back, riding to Peking in the Khans state caravan and playing backgammon provide one of the most memorable parts of Marco Polo and also demonstrate the first stirrings of comedy in Doctor Who, something which Hartnell had extensive experience of in his previous career and which he is capable of excelling at later in Doctor Who. The Doctors first meeting with the Khan, as he reluctantly attempts to kow-tow and his howls of pain prompt the equally-pained Khan to question whether he is being mocked, are played purely for laughs. The later backgammon scenes are also witty, with the Doctor winning an absurdity of prizes but failing to win back the TARDIS the Khan however tells Polo after the travelers have escaped Peking that he would have won it back at some point anyway. The details make the Khans character hes the most powerful man in Cathay, but hes a gout-ridden old man who is henpecked by his wife and is a self-proclaimed bureaucrat. Nevertheless, when facing death at the hands of Tegana, he seems to face it defiantly (as far as I can tell from the recon) and once saved by Polo he coldly informs Tegana that those who oppose him must be humbled and that Tegana must be put to death; interestingly though, he says this in the same way that he says Noglai must be humbled for rising against him, by enforcing harsh conditions of peace. On neither occasion does he seem motivated by revenge as such, but rather by a need to maintain order, suggesting perhaps why he is so well-respected by even the Venetian Polo.
One other interesting thing I realized about watching Marco Polo stems from foreknowledge of The Aztecs despite being in a period of history that Ian and Barbara know of from history books, the Doctor at no point that we see warns them not to interfere. Despite this, the TARDIS crew is directly responsible for saving PoloÂs caravan on two separate occasions, suggesting that had they not been present Kublai Khan would have died at Teganas hand. It is possible that the Doctor does not mention this because he does not consider it interference if the course of history as he knows it is maintained, however accidentally; on the other hand, it is interesting to speculate that if history originally ran differently and Noglai came to power, but the Doctor and his companions inadvertently changed its course. Probably not, but the idea did intrigue me.
Finally, Marco Polo owes its legendary reputation in large part to its sets and costumes. Thanks to the recon, we can at least see these even though no clips survive and they are certainly impressive. Although nearly all of the action on screen takes place at way stations and camps due to the lack of location filming which would have perhaps allowed conversations on horseback, the use of Polos voice-over and illustrated maps of the journey manage to convey the sense that the Doctor and his companions have been traveling for weeks, which of course is the intention. It works well in creating the illusion of a journey despite the fact that really Marco Polo is filmed on only a few sets with no actual traveling on screen. Overall, Marco Polo is well deserving of its classic status.