That's the thing though, pretty much all of those objectives you listed are a part of normal gameplay.
And that's why I personally don't mind most of them. What I'm saying is that because players complain about
all of them, inno doesn't listen.
Some of what are imo the better ones like solve,relics,and scout are the most complained about, but are arguably the best ones for advancing your city.
There could also be more emphasis on spending KP for quests
Right, I forgot about the "spend KP" quests Those are actually the best ones imo. Something you do anyways, something everyone can always do, but with a cost for doing it faster than normal.
Edit: "Gain a spell" is pretty good too. Almost everyone has the MA, and you can get more from visits and the tournament.
Also falls into the category of something
(almost) everyone can
(almost) always do, but with a cost for doing it faster than normal.
Even upgrading buildings is, but I think it could be vastly improved by reducing the number to one upgrade, and loosely basing it on chapter
This sounds a lot like my suggestion above:
"Upgrade a building to (Max level for the highest chapter that you have finished) or* Have 10 buildings of that level or higher"
A quest that either encourages progress, or rewards progress already made.
*It needs that "or" option for players who are maxed out. I try to always keep 1-2 workshop s/residences underleveled, as well as an armory, but that is kinda lame.