Deviant magic
Derek mentioned the random elements in the technology trees. I think the same principles could also be applied to magic:
- spells can deviate slightly in effect, costs, duration, etc
- based on the deviation a spell could be classed of a higher or lower power level; perhaps changing the Fireball III to a Fireball IV spell; thus making the spell more potent, but harder to reach through research
- similar to the tech tree the spell research available would be visible from the start; so grand strategies can be formed based on the starting position for research too