Why did the Fremen expect Paul to challenge Stilgar? Was it just because they saw him as more of a leader now than Stilgar, and it was Fremen custom to challenge the current leader so that he may rise up? Or did Stilgar do something for this challenge to be brought up?
The incident occurred a few pages earlier. Paul, now officially a man, is riding the worm and says they go south. Stilgar asks what will happen if he says otherwise. Paul insists and Stilgar takes this as a challenge to his authority. A tribe can't have two leaders.
You are mudir of the sandride this day,’ Stilgar said. Cold formality rang in his voice. ‘How do you use this power?’ We need time to relax, time for cool reflection, Paul thought. ‘We shall go south,’ Paul said.
‘Even if I say we shall return back to the north when this day is over?’
‘We shall go south,’ Paul repeated.
A sense of inevitable dignity enfolded Stilgar as he pulled his robe tightly around him. ‘There will be a Gathering,’ he said. ‘I will send the messages.’
Note that this challenge is entirely artificial. Stilgar is basically daring Paul to call him out.
‘I am your friend, Stilgar,’ Paul said.
‘No man doubts it,’ Stilgar said. He removed his hand, shrugged. ‘It’s the way.’
Paul saw that Stilgar was too immersed in the Fremen way to consider the possibility of any other. Here a leader took the reins from the dead hands of his predecessor, or slew among the strongest of his tribe if a leader died in the desert. Stilgar had risen to be a naib in that way
Essentially, it comes down to a mix of a few facts.
- Paul has spent all this time training to lead the freman.
- Paul's popularity as the messiah has been growing for a while
- Paul, by completing the trial, is now considered a full adult.
- Stilgar has no doubt that Paul will lead
- In order for Paul to lead Stilgar must die
- There was no malice, it was just all matter of fact.
The "challenge" was essentially a formality. Stilgar had been waiting for the day, he knew it would come, and now the last obstacle to the day was out of the way. Stilgar essentially chose that moment to make Paul the leader, and now to enact that it's time for the next step. Stilgar would have asked anything, said anything, to make the challenge. He was looking for it. If Stilgar has said, it's hot out today, and Paul said, "I guess it's a little hot". Stilgar would have acted as if "little" was a challenge. He was essentially seeking the challenge. From Stilgar's perspective, it's what has to happen next. There is no choice. It might be today or next year but it's next so why put it off.
Paul became a full adult Fremen with the sandride. (emphasis mine)
“And I am a Fremen born this day here in the Habbanya erg. I have had no life before this day. I was as a child until this day.”
“Not quite a child,” Stilgar said. He fastened a corner of his hood where the wind was whipping it.
Now that he has the status to challenge Stilgar (and formally become their leader) Stilgar and the other Fremen expect it, and can't imagine why he wouldn't want to do that.
“There is word from the sand,” Tharthar said. “Usul meets the maker for his test…it is today. The young men say he cannot fail, he will be a sandrider by nightfall. The young men are banding for a razzia. They will raid in the north and meet Usul there. They say they will raise the cry then. They say they will force him to call out Stilgar and assume command of the tribes....“The young men say if Usul does not call out Stilgar, then he must be afraid,” Tharthar said.
And [Paul] thought: I cannot back down. I must hold control over these people.
Paul saw that Stilgar was too immersed in the Fremen way to consider the possibility of any other. Here a leader took the reins from the dead hands of his predecessor, or slew among the strongest of his tribe if a leader died in the desert. Stilgar had risen to be a naib in that way.
I'm unfortunately at work and won't be able to support with quotes. Hopefully my memory holds true and kind people like @Valorum can provide the relevant sections.
I have to respectfully disagree with @Valorum's accepted answer. This gives a good overview of the event that made the challenge possible, but Stilgar's conversation with Paul was not perceived as a slight by either of them.
@swbarnes2's answer gets closer to the source, but misses some key details.
The Sisterhood had been implanting the messiah myth into the Fremen since they became a unified people. When the Atreides came to the planet, the rumors put in place by the Supreme Reverend Mother Gaius Helen Mohiam gave them enough hints to nudge the Fremen into believe he was the one. Future interactions with the Shadout Mapes (the assassination attempt) and Kynes (on his stillsuit fitting) reinforced that belief.
During their first run-in in the desert with Stilgar's tribe, there was (for Fremen) open debate on him being The One. After the duel with Jamis, some even believed a leadership change would be forced then (though it was assumed that it would happen through a marriage of Jessica and Stilgar).
There were later conversations with Chani about how the tribe wanted him as a leader, but he was not yet a man and "couldn't do what the least of them could" (e.g. call a sandworm).
Riding the sandworm was the last obstacle to what the tribe had been clamoring for for years. The conversation between Paul and Stilgar on the worm should be read through the subtext. Stilgar was loyal to the tribe and duty to the tribe above his own life. Paul was looking for another way, and hoped to fulfill his father's dream of uniting the tribes under the Atreides banner.