John and Cortana’s relationship is, in essence, one long retelling of The Ballad of Tam Lin.
The Ballad of Tam Lin tells the story of Janet, who is warned to never go to Carterhaugh, a keep she will inherit, because the keep has been taken over by the fae and the fairy Tam Lin lives there. So, Janet, immediately puts on a green dress, goes straight to Carterhaugh and summons Tam Lin. Tam Lin explains to her that he is, in fact, a changeling, and while he was formerly the favourite of the fairy queen he is now destined to be sacrificed as part of the fae tithe to hell on Hallowe’en. Janet saves Tam Lin from the fairy queen by pulling him from his horse and holding onto him as he is forced to assume many forms and ultimately saves Tam Lin and reclaims Carterhaugh.
John has always been a changeling character. He was stolen as a child from his family by Dr. Halsey (the first fairy queen character of this adaptation), replaced with a sickly copy, which is a common theme in fairy mythology as a whole, and taken away and turned into a Spartan, something which many people believe is not quite human. The Spartans, and the Master Chief in particular are routinely associated with the mythological and inhuman. They are called ‘demons’, ‘war gods’ and ‘monsters’, the armour they wear is called ‘mjolnir’ after Thor’s hammer. John himself is well aware of his conflicted relationship with his own humanity; once absently differentiating himself from other UNSC soldiers by referring to them as ‘humans’ in Palace Hotel and then admitting to himself that “[h]e may have thought of himself as having been human, perhaps even that he was still human”. Later, in Halo 4 he distinguishes soldiers, who protect humanity, from the humanity they protect. John is and always was Dr. Halsey’s favourite Spartan, just like Tam Lin was the favourite of the fairy queen. But, John (and all the other Spartans) were chosen and trained with the intent that by sacrificing the Spartans’ chances for normal lives, they could save the rest of humanity by ending the insurrection and then by defeating the Covenant. They are, metaphorically, Dr. Halsey’s tithe to hell.
And, of course, John wears a characteristic green set of armour, which he has kept even after the other Spartan-II’s have started to use the more varied updated versions of Mjolnir armour. Green is a colour commonly worn by and associated with fairies.
I’ve mentioned before, and will mention again, that John is a fundamentally passive character. While he is a player character, making it easy for the agency of the player to give John a semblance of narrative agency he doesn’t have, he is partnered with Cortana without any say in the matter and spends four games following Cortana around and doing everything she says. And the novels and various other media doesn’t vary significantly from this pattern. This is very much in line with Tam Lin’s role in the Ballad, being fought for and then rescued by Janet.
Cortana, on the other hand, spends those four games discovering and investigating two major forerunner relics (Halo and Requiem) defeating Guilty Spark and the Didact, saving the Earth and bringing John home. She, like Janet, is the consistently active character whose decisions drive the narrative. Also, like Janet, Cortana’s choices are also what bring her into contact with John. Before being assigned she asks “Which [Spartan] will be mine?”, to which Dr. Halsey responds “Which one do you want?” After meeting John, and unearthing his background in the Spartan program, she decides that “whatever the Master Chief had been through in the past… it was done. He was in Cortana’s care now. She would do everything in her power… to make sure nothing ever happened to him again.” Not only does Cortana protect John, but she has been described, specifically, as the guardian of John’s humanity. The thing which keeps him human.
Once John passes from Dr. Halsey’s hands to Cortana’s, her role as the Fairy Queen is passed to the Forerunners (and their still living AI on the Halo Rings) and the Flood. Although there is no direct analogue to the shape-shifting Tam Lin undergoes in the original myth, Cortana does protect John, she prevents Guilty Spark from setting off Halo 04, sends him back to Earth while she remains on Halo 05, watches over him while he spends four years in cryostasis and then ultimately saves both John and Earth from the Didact.
When Cortana defeats the Didact in orbit over Earth she is returning them from the Forerunner (fairie) world of Requiem to Earth, which is the most unequivocably human space in the narrative. Although John’s home would more properly be either Reach, where the Spartans were trained, which they though of as their home or Eridanus II where he was born, Earth, as Lasky points out in the penultimate cutscene of Halo 4 is home to humanity, even to those humans who don’t live there, which makes it the correct place for Cortana to bring her Fairy Knight to ensure he is safely returned from the fairy realm of Requiem to the human one on Earth.
At the end of Tam Lin, Janet returns triumphantly to the recaptured Carterhaugh with her newly freed fairy knight. Cortana, on the other hand halts the Didact’s assault on Earth, brings John home, says her farewells, and dies. Which is seemingly far less triumphant. But Cortana’s death should be viewed in the context of death in Halo and in Halo, dying is what heroes do. Captain Keyes, Chyler Silva, Kurt Ambrose, Randall Aiken and the members of Noble Team all also died achieving their goals and saving others. Cortana’s death, in the context of how Halo’s stories are told, establishes beyond question that Cortana is a hero on par with all the others.