- start war with another faction (those bastards killed my wife/husband/child/parents/cousin-four-times-removed) within the next x years
- make peace with another faction (my whatever relative lifes in their land)
- raze a city of an enemy (same reasons as above *g*) within x turns
- don't build any shrines of a specific type for at least x turns
- get x shrines of ???
- have a certain amount of goldmines (i.e. for stay-at-home heroes furthering gildar production - they won't waste their talent for someone without enough mines)
- same with libraries, metal mines etc.
- my daughter wants a pony (no wargs - horses! *g*)
and so on.. but please make sure the requirements are very clear, can be easily reviewed and the champion reminds you frequently if you don't react fast enough. Also, I think most of these requirements should be full-fillable within a certain amount of time, otherwise you have to them and then search the whole world for the wandering champion. or let them camp at one of your cities paying them x gold per turn for waiting, so you have an incentive to finish the task quickly.
another idea: after serving you awhile, your champions offer you personal quests on their behalf (like in dragon age, when you befriended your companions enough)