By randomness, do you include enemy encounters? Because if so I do want to bring-up Xenoblade again. Again- not an action game, but one of the great things about the series (particularly X) is that everything is deliberately placed, including enemies. There's not one single random encounter in the series. So even smaller fights with "generic" enemies you can feel the intention behind the fight. Whether they affect the fight mechanically (enemies too strong for you placed on the most direct path the first time you enter the area, but also next to, say, a cliff they can be knocked off of or perhaps a slightly hidden path placed for perceptive players to use to sneak past them), or just add cool flavor (a bigger enemy variant paired with smaller ones looking like it's leading them or even sitting on a throne in front of them, or a strong but passive enemy looking directly at slightly weaker but aggressive ones, as if to watch over the fight when you inevitably fight the weaker one).
I think one of the follies of open world design is the lack of intention. Grand Theft Auto popularized the idea of the "sandbox" open world- you make a big place and you put pieces there to let things happen. They're not set, and emergent gameplay arrives. That has its own appeal, but it also feels like open world games lean so heavily on it that people see it as an inherent aspect of Open World design. But I think it's very possible, with the Xenoblade games as proof, to instead make an open world that isn't a sandbox for things to happen, but rather a massive intentionally designed area where each corner of the game world has things the developers want you to experience. Hell, I don't even need to point to xenoblade, 2D open world games like metroidvania or the first Zeldas were like that too.
And if you have that sort of intention in your level design, it can benefit whatever combat you have, Action or otherwise.