If you get as chance give AOE2:DE a shot, I feel like it's what you are describing. It's impressive how many randomized game parameters it has... they even included a randomize button.

https://i.imgur.com/xbbXKdq.png

Additional you can add mods such as 'Random Costs' where units and buildings have random costs so standard build orders are impossible. Because the game is still being updated, people are making new maps and mods, there are often new strategies being discovered frequently.

But to me, the best part of the game is playing with a group that are all a similar skill level. Fortunately the game has a match making system letting my mates and I get paired up with others.