Personally, I think killing Cortana was a great move story-telling wise, and she should not be brought back. Don't get me wrong, I liked her a lot, I loved the whole story the Master Chief and Cortana had all built up, and their goodbye was emotional, and marks a future for the character.

Take another Pixar storytelling rule:

"What is your character good at, comfortable with? Throw the polar opposite at them. Challenge them. How do they deal?"

Getting rid of her will force the Master Chief to do something else: Adapt. Now that she is gone, one of his closest links to humanity, how will he deal with this all? There are so many factors at play, hinted at, and hidden from us, that the Master Chief will not be someplace comfortable once Halo 5 rolls in.

It could force his character to evolve, to change, and to perhaps, regain his humanity as 343i vidocs have all hinted at. They stated Halo 4 would be the first act in John's personal story, so with everything going on and no longer having Cortana with him, he would have to act a lot more independently rather than needing someone else.

The Master Chief is a proven hero, I agree, but it relies on other things beside combat. Most of the times, he usually followed either Cortana or his superior's orders, and I'm of the belief that a person never really stops learning. He may have yet some road still ahead of him.