For example: We’re looking at having it be a bigger deal when a City Levels up and giving them points (almost like a character) to put into traits like food production, research production, etc. We can do that because all we have to do is apply something like this:
How about mutually exclusive buildings instead (or in addition)?
For example, when a city reaches level 2, you could get the option to build a Food Production building OR a Research Production building, OR a Whatever building, OR....
At further level-ups, the bonuses could be increased, new choices could be offered (or you could have one large set of options, and each level-up gives you one pick from it), or you could choose to improve a current bonus or get a new bonus at a lower value (e.g. at level 3 you could have "lvl 3" Research bonus, or {"lvl 2" Research bonus + "lvl 1" Food bonus}).
This way you'd also get the ability to have more varied cities, but it'd do so in a way that gives a stronger visual indication (of course, that also means new graphics...).
The random trait idea also seems neat.