What a neat idea. All kinds of cool ordeals come to mind, with varying levels of cooperation needed from neighbors/Pantokrator:
Walk Upon Burning Coals
Win a battle under the Heat from Hell BE.
Leap of Faith
Cloud trapeze/teleport a commander into a specific province and survive the ensuing battle.
Wrestle a Gator
Have an un-equiped commander kill a Bog Beast in melee combat.
The Ring of Fire
Conquer a province using only Fire Bolas. No damage of any other kind is permitted.
Tame a Lion
Obtain a Kithaironic Lion by whatever means possible.
Swim Shark Infested Waters
Have a non-amphibious commander survive combat under the Shark Attack BE. Oh, and he's gotta kill at least 1 shark.
Baptism by Fire
Kill a Fire Elemental with an indy priest.
40 Days and 40 Nights
Defeat an enemy army with nothing but starving units.
Vision Quest
Traverse a lone commander to a distant province, and have him return safely home.
Climb the Highest Peak
Obtain a fortress in a true mountain province.
Save a Virgin
Defeat an enemy such that at least 1 of his blood slaves is left on the field.
Slay a Dragon
Self explanatory. Drakes don't count.
