No, PCs need not all level at once
Milestones are gained at the end of narrative arcs, but the end of a narrative arc for one character need not be the end of the arc for another. Let's do some examples:
Dr. Van Helsing, the renowned monster hunter and PC #1, arrives in a lakeside town on the heels of his long-time nemesis, Dracula. His assistant has been recently murdered, so he picks up a new one in the form of PC #2, a plucky local high-school student.
In the course of their adventures, the high school student must come to terms with the presence of the supernatural. Eventually, after a suitably climactic scene and sufficient character growth, the GM tells the player of PC #2 to replace their 'Clueless' aspect with something more appropriate, and gives them rewards for meeting a minor milestone. Van Helsing is already familiar with the world of the supernatural and participates in this arc only as a supporting character. The player of PC #1 recieves no rewards for this.
Also in the course of their adventure, Val Helsing begins to realize that he is actually responsible for the death of his last assistant. He abandoned the assistant, who could have otherwise easily been saved, in order to not lose track of his adversary. When the assistant survived, but wanted out of the business, Helsing murdered him to keep him from later being used to garner information about their operations, then repressed the memories.
He has now also realized that, if they continue to work together, he will probably betray his new assistant at some point, if they don't realize the truth about his past assistant first. He spends a scene smoking the last of his father's prized Bulgarian cigars, perched on a crate in his basement where the corpse of his assistant is kept, along with what the professor believes is the rest of the evidence. Using the butt of the cigar, he starts a fire and walks out, sacrificing the last of his humanity in the pursuit of Dracula's destruction.
This is a major character decision, ending a significant arc, and so the player of PC #1 receives a major milestone. PC #2 is not involved in this arc, except as an unwitting antagonist, and so they don't receive a milestone here.
So, that's how milestones might be for one PC and not another.
It's important for PCs to receive equal narrative time
While PCs might not get milestones at the same time, it's important that they get roughly the same milestones on average, not only for game balance but also because of what milestones are tied to.
Milestones represent, in a way, screen time. Every scene should move something forward, and both successful and unsuccessful die rolls should lead to arcs ending eventually, one way or another. That means that if two characters have received a significantly different quantity of milestones then one of them has gotten to matter a lot more than the other, and that's not usually conducive to the left-out player having fun.
So milestones can be got for different things, and at different times, but they should usually add up to about the same for everybody, on average.