Hmm.. I agree with the observation of "Go exactly here and kill stuff" quests become dull if they are the only type encountered.
You mentioned wider area searches? I would like to make some further suggestions.
If players can be given quests that do not limit the completion location to a single non-movable location, I would suggest locating the goal thus:
1 - Bound a given area by lines, tile types or enemy types and randomly choose one tile to complete the goal.
*** Go to the Keral Forest (region of forest named on the map overview) and kill the Jabberwocky
*** Go through the Ulian Planes (a large plane) to the hills of Bilgor ( a small set of hills in the Ulian Planes) and find the hidden treasure.
*** Enter the Worgan Deeps (deep forest occupied by lots of Worgan) and kill the Worgan Den Mother
2 - Describe the area to the player as a location with a certain tile type
*** Find the cave occupied by the Dyrzat and bring back its eggs.
*** Search the shores of the Broade Sea and discover the whereabouts of the Dandy Maiden
3 - Create an NPC unit that flees from the questing player's units and flees from the players territory
*** A thief has made off with the secrets of our Library, find him before he sells that information
*** The assassin has escaped the Royal Guard, pursue him, find out his master, and then dispose of the body.
4 - Create an extremely strong NPC unit that attacks the questing player's units on sight and slowly approaches and attacks their villages.
*** The chant of Qizso has awaken an ancient mountain god. Slay the beast before he destroys us all.
*** Your financial dealings have not gone unnoticed. Droknan has sent his best assassin to reclaim his debt.
5- Create a landmass that is invisible unless a unit is less than a certain distance from its shoreline (regardless of sight distance)
*** Stories tell of a forsaken land far to the southwest that no mapmaker has ever drawn.
6- Designate one player unit as the target of the quest. Quest is complete when the unit is under command of the sovereign.
*** Rumors tell of a hero amongst the soldiers, one who acts in secret, serving the empire well. Only under command of your sovereign will you discover this soldier's identity.
7- Designate a random traveling NPC as the target. Quest is complete when the player recruits the NPC.
*** Legend tells of a wise old sage, traveling the world with his dog. Surely his wisdom might aid our cause.
*** After the fall of Uqipwe, the Earl of Bastuen lost everything. Now he roams the world as an adventurer avoiding politics and the fate of nations. Find this man and you will find the answers you seek.