: His Legend could be awkward for the government or ONI if he was to take a
: stand against them. He doesn't need to betray them, he just needs to voice
: a different opinion. His legend gives his opinions weight. So his legend
: has to be undermined.

This right here is it.

: Locke would have been lied to but he cares about the truth. If he had
: reservations about John's "treachery" then he would hunt for the
: truth. He would hunt for the real John.

: I wouldn't want to spend 3/4 of the game trying to take down the Chief only
: to work out that the Chief wasn't a traitor until near the end of the
: game. We know the Chief isn't a traitor so spending too much time as
: another character who hasn't worked that one out would wear thin pretty
: quick. Just like it was annoying to play as the Arbiter and to take
: forever to work out that he was being played.

: I would prefer if Locke had some inkling or reservation early on and was seen
: to be open to the truth and interested in finding out for himself. That
: way I wouldn't feel that I was just treading water, shooting things, until
: the big reveal finally happens.

Yeah, my guess for the plot would be something along the lines of...
1) Play as chief, set the ground for his story arc, where he is, what he's doing. Fight some forerunner probably.
2) Jump to Locke. See his situation, his commission. Fight some covenant, searching out the chief. Uncovering bits and pieces about John, conflicting with reports he's been given from ONI.
3) Cross paths with the Arbiter. Many things change about his opinions of the chief. But he has to remain loyal to ONI. Highly conflicted in his mission.
4) Back to chief, carrying on his arc.
5) Locke finds chief, reports to ONI. Locke sympathizes with chief, but ONI betrays Locke. Backup agent takes control and tries to get the chief; chief does what he can not to kill humans but save his own hide - and Locke's.
6) Chief & Locke team up to complete chief's arc - avoiding ONI, Covenant factions, Forerunner, and Flood.
7) "Finishing this fight."
yadda yadda. Something like that :P.

This heavy on story there will need to be twists and turns and betrayals and unexpected characters and more. But there's no way they could villify Chief outside what we know to be false allegations and propaganda from the 'true' bad guys.
In this case, ONI is technically a 'good' guy for humans, but in humanity we have good and evil, and ONI could be the bully that wants their way, wants humanity to follow them instead of the chief, thus all the proganda to take chief down; and they still have to deal with Halsey. But John knows too much about everything Forerunner AND he lost Cortana. So he's got enemies on every side. But he still has to be the ultimate Good Guy.

It'll be interesting how they set everything up. Just really hoping they don't botch it or make things to predictable and canned. I liked Halo 4, but I think it may have had the most critical reception of the Halo game stories in the community... =/