Had a few random ideas.
For a future legend the MC has a super easy time getting to the spot where the legend will be but has to wait a bit and fend off others who want to meet the legend instead. Like the game king of the hill.
The MC might want to try camping out in the forest and brings one legend with him like if he chooses groudon she would make a cave to have fun in.
Celibi could get along with the force of nature who likes to prank like her when they both prank each other at same time and team up to prank the other legends.