Pherim: Many different things to choose from is not what I would call creative, necessarily. While being a great game in itself, the only "creative" part of Age of Empires 2 would be making new scenarios - but this is not really ingame creativity.
To a certain extent, I would say, Open-World-Games like the Elder Scrolls series could be considered creative because of how they allow the player to play their very own story and do whatever they want if they choose so. Of course, the modding possibilities are a whole other thing altogether, though again, this is not exactly happening ingame. Other than that, I liked the building part of the Sims always a lot more than the actual playing. One could say that building a castle in Stronghold is kind of creative, but you are relatively restricted by the purpose of it. Rollercoaster Tycoon, however, can be a very creative experience. You are not required to use themeing parts in a way that they actually make sense or look good, but it is just way more fun if you think a little about what your park should look like and try to build it as beautiful as possible. In the second game you certainly have enough parts and possibilities to build basically anything you want, but it can become very fiddly at times. Still, I cannot recommend this game enough.
However, most games are only creative within the boundaries of their own rules and provided possibilities. Finding ways to overcome these either within the original game or from outside with mods is where the real fun begins, in my opinion.
I have to disagree with you about AoE2 (and this is one of the very few sites where discussions take place, and not flame wars, as you probably know, so I'm not trolling). Creatingg different build orders. Like how many vills on which resource to get X number of X units in X minutes, and doing stuff like making a small box around your mangonnel so its minimum range is removed etc does require a lor of creativity.
Of course, modding is an entirely different type of creativity. Most people don't have the skill for it but those who do can, as you said be free from the limitations of the games rules. While modding allows a higher degree of creativity, I still believe RTS games allow the most creativity within the rules of the game.
RTS=lego bricks. You can do a lot, but following certain rules.
Modding= plain canvas. You are not limited in any way to express your creative freedom.