How are your players "maxing out perception"? Are they aware that it is not a skill and can't be increased with skill feats? I've seen a few players get confused by that. Are your players all taking Canny Acumen for Perception as their first general feat? That feat would make perception proficiency maxed compared to their skills at some levels, but even then, a low wisdom character might prefer another strategy.
Other than that, it seems mostly left up to the creativity of the players and gm. Perception is the most common way to decide initiative, as there are a lot of situations where you are just watching out for threats. Dungeons tend to encourage using mostly perception or stealth. That's ok.
However, PochiPooom has given quite a few examples, and I'll add a couple more based on what I've seen in online games.
If the players are trying to track a creature, they can use survival as they are actively looking for it using specific methods.
In a social encounter in which they are trying to convince an npc that they bear them no ill will, when they are, in fact, ready for a fight, they might use deception to hide their intentions for as long as possible while they try to get more information, or diplomacy, if they are honest, as they try to keep the other calm and to pay attention to cues in the conversation.
Gladiators literally jumping into an arena or fighting pit might use Athletics to see who manages to land on their feet and be ready to fight the fastest. (That one I just made up.)
If you want to make full use of this new rule, it's up to you as gm to put the players in situations in which they are not just walking through a place trying not to get jumped, whether it's because there is room for creative ways of attaining some goal or because you are requiring that they do some specific tasks to keep moving forward. Encourage the players to be creative in their descriptions of what they do, and pick a skill based on that.
Also, note that scouting gives a +1 to initiative, not perception, so other players might use other strategies during that time.