Looking at existing randomizers, and what you are asking for, I feel something similar to the Symphony of the Night Randomizer would be fun.
To explain, it shuffles relics, which grant abilities that unlock more areas to explore. These relics are only shuffled into specific locations, meaning for progression, you only need to check specific locations. There are still "dud" relics to find, but this removes the scavenger hunt that causes such a wide range of times in randos like Link to the Past.
Ideally, the game would have a map with multiple different paths (some shortcuts) that unlock depending on the progression items found. So while players could learn where they need to check, the order places unlock could vary from run to run.
The other appeal of the SotN rando comes from the rest of the game. There are hundreds of weapons and other gear in the base game, and the rando leads to finding and adapting to different combat each run, based on where things appear. This also adds a potential risk vs reward system... do you explore the optional areas to maybe find a better weapon?
I think Yuurand does the opening map design well, and I've done randos with huge numbers of weapons to try out. Something that combines the two designs might be what you are looking for.