In a nutshell, each time the evolved template is gained, the creature improves as follows:
- +1 to natural armor or deflection (if incorporeal)
- +2 Strength (if corporeal) and +2 Charisma
- One random spell-like ability from a list (or increased usage of the same ability)
- Fast healing +3
Looks a good start.
How about adding an increase to Spell Resistance to that list?