It’s often bemoaned that many games (e.g.: Fallout) are filled with quests which consist merely of killing and/or fetching an item.
What other possibilities are there? What general principles underlie the possibilities?
Explore; investigate.
Witcher 3 involves lots of these. Go to this abandoned town and find out what’s going on here, and report back! Figure out who killed this person, and report back!
In one MMO that I’ve played (Champions Online), they have “escort” quests, in which you find an NPC at a particular (unsafe, supervillain-infested) area, and have to escort them to safety, within a certain amount of time. The NPC walks along a more-or-less straight course towards the safe area, and it’s up to the player character to fend off the baddies, and keep the NPC alive.
It’s a nice little twist on the usual quest, though there isn’t much variety in them within CO.
Problem with explore/investigate is that they’re usually not much different than fetch quests. Go to location, [kill/talk to] NPC, return. Or go to location, find correct thing to click, return.
But, honestly, that should be fine for minor side quests. Returning with six chicken teeth or some farmer’s lost shovel is supposed to just be a small diversion for incremental gain. It’s the larger quests where you want the option of shooting your way in to get the prize or sneaking in or talking your way in past the guards. At the end of the day, almost all quests boil down to “collect objective, return for reward” and what separates the good ones from the ‘fetch quests’ is a lack of options or things between getting the quest and finishing it.
Thinking about it, another class of quests could be the “creation” quests: forge a sword, research a spell, create a functioning settlement – something where the reward is in the creation as opposed to returning to Friar Bob for your handful of gold and three charge healing potion. That still has some of the same components (you need to get the sword metal from the trolls in the cave) but changing its conclusion makes it feel different even if the mechanics are the same.
↑
It’s him! THIS guy is the reason game designers still make escort missions. I knew he had to be out there somewhere, and now he’s broken his silence and shown his (pseudonymic) face.
Break out the wet trout and let the slappings commence. Sorry, kenobi 65, it’s nothing personal — we as a polite gaming society must simply uphold the greater good, and nobody (except you) has ever liked escort missions. Seriously, read that thread; there’s nothing by way of dissent. Escort missions being terrible is a fact as empirical as climate change, and deniers cannot be tolerated. 
Escort quests are the worst. Starcraft II had one where the “helpless escortee” was a 5000 HP death machine, and it still sucked so much that the best way to beat that mission was to build buildings around the death machine so it couldn’t move.
I think what sets the good quests apart from the bad ones is that there are multiple ways of accomplishing them. Like, say, suppose that the quest is “Stop the bad guy from completing the end-of-the-world ritual”. Maybe you do that by going in guns blazing and just blast him. Maybe you do it by sneaking in and stealing the Evil McGuffin from under his nose so he can’t complete the ritual. Maybe you do it by finding the Good McGuffin that counters the Evil McGuffin, and bringing it to the ritual location. Maybe you do it by getting ahold of the ritual yourself, and modifying it so instead of destroying the world, it moves the whole world to a different dimension where it’s safe from the destroy ritual. Or maybe the game is on rails, and going in guns blazing is the only way the game will accept.
laughs
To be clear: I found them to be at least a little bit of a change of pace when I first encountered them in CO. But, once I realized that they were all pretty much the same (the only “variation” I ever saw was that sometimes the NPC was a capable combatant), the novelty wore off.
I won’t go so far as saying that I particularly like them. 
But, they do fit the OP’s request for examples of things other than the “kill” and “fetch” missions.
Escort missions of the type you describe suck. I don’t mind them when the NPC can be directed to wait somewhere safe while you clear an area and then move to the next safe point though.
Roleplaying/Diplomacy quests. You’ve got X NPCs who want the same McGuffin or for you to make a decision that might shaft all of the others. Pick a side, or stay neutral, or fuck 'em all over, try to compromise, try to understand what makes them all tick and so on. It’s even more rewarding when the dialogue and supporting materials provide hints without spelling everything out, that way you feel clever for understanding what’s really going on or why that apparently best solution really isn’t. This goes very well with moral quandaries, be it in terms of “all the options have something terrible about them, pick the least shit”, or “your duty is X, but the better outcome/more moral decision is Y, and the choice that gives most loot & shit to you personally is Z but you have to eat a bowl of puppies. Choose. We’ll wait.”
Management quests : if you’ve got a castle/stronghold/kingdom/tavern/whatever, find some crew, train the crew in this or that way, defend them from outside threats and so forth. All of which may involve fetch & kill stuff, but it’s for your own benefit and by your own choice, so it doesn’t feel quite so abstract or futile.
Exploration quests : you’ve got this sprawling forest/dungeon/city/swamp and we need X which we know can be found somewhere in it. Find X, either by wandering about or talking to the locals or using your own skills & magic or hiring folks to find it…
Survival quest : not much different from a kill quest, but typically more dangerous - infinite waves of enemies, timed kills, protecting McGuffings by drawing the mob’s attention all fit in there. For once you get to defend and use all those mines you’ve been picking up !
Patrol quest : another variation on the straightforward “go here, kill that” quest - go to X spots, deal with whatever comes up along the way - maybe it’s bandits, or people in need of help, or bandits pretending to be people in need of help, or just travellers with a story, or an interesting thing you might want to explore but that exploration conflicts with your patrol duty, or something that would require you to cut the patrol short and warn someone about it but you’ll get chewed up/stiffed on payment if you do…
Scout : similarly, this is a fetch quest but disguised. Instead of fetching an item, you’re fetching information or photos. Maybe poison rations or find a safe path through a minefield along the way.
Some relatively recent MMOs have done “public” quests as well.
These tend to be elaborate multi-stage affairs with significant variation on the goals.
For any stage, maybe you have to kill a number of mobs, or destroy objects, or protect the players attacking the objects, or protect npcs or an object, or gather widgets, or protect the other players gathering the widgets, or kill a massive boss mob.
I remember LOTRO had a “kill 10 boars in 30 minutes” quest where the joke was, that there were no boars in that zone. So it was basically free xp on a timer.
I think the key is in wrapping the fetch/kill quests in a good story so you feel both motivated to do the quest and that you are achieving a worthwhile in-world goal.
Why am I fetching these things?
Why can’t you fetch them yourself?
Is the reward appropriate for the effort/time invested?
If these questions are answered well then the quests are ok. The best fetch quests are ones where you don’t even realise it is a fetch quest.
A good fetch/kill quest for me would be one where I, say, meet an NPC armourer who tells me he can make me some good boar skin armour but he’s all out of boar skin and his latest shipment hasn’t arrived despite leaving over a week ago. I don’t even have to be asked to go and investigate what happened to the shipment and to kill a few boar while I’m out there, I already want to do it.
Just Cause 3 has a fairly wide variety of missions and activities. Sometimes you’re defending an object or person, sometimes static and sometimes moving. There are activities where you have to drive a bomb and blow stuff up (jumping out at the last minute); or racing a car or motorcycle or aircraft or wingsuit; shooting challenges; plus whatever other stuff you make up for yourself, since it is pretty open-world sandboxy.
Whatever its shortcomings, there’s no lack of variety.
And the answer to those is often “off” in both directions: the almost stereotypical “kill a rat in my bar’s basement in return for roughly eight years of bartender wages” bothers me more than the cheapskates, actually.
Borderlands 2 has a quest where a there is a dead body and four suspects- you need to question the witnesses and then accuse the appropriate suspect of the crime.
Another quest involves questioning four people that are in a “Truxican Standoff” and then shooting the one that actually stole the MacGuffin.
Good quest but almost surely a copy of the same quest from the original KotOR.
For quest variety check out The Secret World. Investigation quests that include looking stuff up on the actual web are interesting.
I’m currently playing Watch Dogs 2 on my Xbox One and I like how most quests have multiple solutions… Do I sneak past people, or kill everyone, or try to hack stuff from a distance…
World of Warcraft has a few where instead of you getting the quest you become the questgiver (in Hillsbrad Foothills)
“Hail, Tailor Wynn”
“Hail, traveler. Looking for armor? I’m afraid I’ve run low on supplies; all out of boar hides you see.”
“Dude, I saw a bunch of boars in the woods, I’ll get some!”
“Well, wait, that’s not what I was–”
“BRB with ten sloppy wet still-warm boar hides! Get ready to make me armor, bye!”
“…” “Damn it, I wanted to close early today.”
In the first Star Wars: Knights of the Old Republic, there is an optional quest during your padawan training where you come across a dead body, and a Jedi Master asks you for help solving it. There are two suspects, but having differing accounts as to what happened. You had to talk to both of them, then talk to the other, kinda like 2 separate interrogations that got more intense as you moved on. You got to pick whoever you thought did it based off of their stories (stat bonuses on your character’s charisma would open up different avenues of questioning). There was also a droid nearby to use for weather conditions, etc at the time of death.
There was an actual guilty party, and you could let him go free if you failed the quest. Presumably, your padawan status wouldn’t let you use the Force to compel them to tell the truth.
The escort mission I loathed the most was the one in Resident Evil 4. The missions with Ashley were pure torture. At least in the Star Wars MMO, on the escort missions, you could choose to kill the person instead of save them.
I brought that up in post #15. 
Yup. Fuck “escort” missions. If your charge was ever not actively trying to get themselves killed, they might be tolerable, but that has never, ever been the case that I’ve found.
The GTA games have always been fond of “Locate, chase, and kill” missions. Really just a twist on “Kill and fetch” and frankly, often as difficult and frustrating as “escort” missions, but it’s something different.