However, if a modder changes stuff with a very good understanding of current AI behavior ... then there are quite a few areas where re-balance or added mechanisms can enhance AI competitiveness without adding AI bonus.
Exactly. Some of the better balance mods see what the AI is already doing, and adjust the game in a way that encourages the player to follow those same strategies.
The AI picks techs almost randomly, while the human will beeline up one side of the tech tree to get key techs. Solution? Add more tech interdependencies so that it becomes impossible to go straight for a single tech.
The AI won't expand as fast as possible, only settling a new city once it has a small buffer of Happiness to where it knows it won't go negative by doing so. Solution? Change the base unhappiness values and the amount you get from population so that the player will think twice before settling a new city.
The AI won't use Avoid Growth to keep cities from growing past small sizes, while the humans used ICS to win easily. Solution? Make it so that ICS doesn't work and the player goes back to playing like the AI does, with cities growing at normal rates.
-------------
The Flavor system is actually pretty flexible, because it doesn't care exactly WHAT the bonuses of a building or unit are, as long as you can fit them into one of its categories. If I make a national wonder that gives the owner a chance of stealing techs it doesn't have from the other players, then the AI doesn't need to actually understand the effect of the building. You just give it FLAVOR_SCIENCE, and the AI thinks "hmm, I need more science... okay that building should be good for that." It doesn't care exactly how the effect relates to science.
Or consider yields, which are something the AI already understands. Maybe you add a new unit action allowing a worker to plant a forest on certain terrains; the AI only needs to think that doing this action will add production to a tile. Even if it has no clue what the actual effect is, it'll choose that action when it thinks it needs more production.
The AI will have problems if the thing you add requires a conscious decision, but if the effect is passive, random, or strictly yield-related, then the AI handles it about as well as the human would. That leaves a lot of room for mods to work with, improving the game without crippling the AI.