I totally agree that we need more diversity when it comes to townhall quests. Right now there are only kill boss X and find artefact Y, which actually feels exactly the same. This is a good solution.
I could imagine some easy ones at low levels where you just walk from one area to another with a person. This can be used to encourage people to explore the map more, and should be timed so they are quite difficult (ie going to New Anthur at level 9-10ish)
Some harder ones with random highwaymen encouters, similar to Safe Passage.
Finally really difficult ones could be scientists/researchers wanting to research Trolls, collect ice samples from Wyvern Mountains, collect rocks from The Deep Cauldron, etc. In these quests you have to take your weak follower to extremely dangerous locations and keep them alive while they go about their specialist research.
Really would support this idea being implemented in some form.