I enjoyed the AOEIV mastery system and liked the challenge of having to progressively beat harder AIs after completing 5 or so challenges in between to eventually complete "qualification" for a particular faction.

The kind of things I would be looking at for a mastery would be:

TEC Rebel:
Mastery lvl1: Use a scout with autoscout turned off to find 2 minor factions
Mastery lvl2: Upgrade a Kol class ship to use X upgrade and then kill X x10 ship type with it.
Mastery lvl3: Use missile frigates with X upgrade to kill X enemy ships without losing X frigates.
REWARD: New profile portrait
Mastery lvl4: Create a battlegroup using X command and set them to defensive formation and withstand attacks from two capital ships at once
Mastery Lvl5: Competency Qualification Win against an easy AI with a TEC rebels
REWARD: Camo skin for Marza Dreadnought
Mastery Lvl6: Kill two enemy Capital ships with Kodiak cruisers
Mastery Lvl15: Final Competency Qualification Win against an hard AI with TEC Rebels
REWARD: Mastery complete shown to others on portrait and A unique alternate Kol class model.


Bear in mind each mastery must be done in a separate game and in order.
Each mastery should have a reward as people may take more than one go to finish the mastery level at each level.