I'd probably keep Kirk, Spock and the Enterprise in a reboot. Try to figure an angle that allows the show to keep Number One, maybe as someone who thought they were in line for command after Pike was promoted. She doesn't see herself as a subordinate to Kirk, but a competitor for the Captain's Chair, also she handles the helm.
Would Number One still be on the Enterprise? The Talos IV mission was "13 years ago" during the first season. Majel was around 30 then, so the character might be in her 40s by the time of Kirk's command. She might be in charge of a sister ship to the Enterprise.
If still on the Enterprise, perhaps she's the chief engineer by then, as the most experienced officer during Pike's day. The "coldly logical" aspect of her personality, which I never really felt through the performance, could be eliminated. And she'd need a real name maybe.