They are labeled and yes they are similar as you put it.  Though having played both Witcher 3 and BotW the conveyance of the same task across both games has different effects.  When a person mentions that something happened in a place in W3, the bubble pops up on the map.  In Zelda, they mention the place and you find the(usually reasonably close) area yourself, then search it.  It's a subtle difference, as onionberry puts it; Zelda's method peaks your curiosity and involves you in actively finding the spot.  W3's method just feels like another task - albeit probably a damn fine one.

I disagree. While I enjoy open-world games, there's no reason to do that. At least not exclusively. A few quests okay, but if some NPC sends you after some item and is vague and cryptic about it, then he can go get it himself. I'm not getting that tankard for you, prat.

There's another genres better suited for that, point-and-click and adventure games.

Xenoblade Chronicles X did this quite a bit actually. sidequests often had you go out to find certain pickup items in the wild, and would tell you what continent they were at, but nothing else. You then had to venture out just trying to find it on your own, or resorting to the wiki to find the exact location (which I am guilty of). You could also be given hunting missions that require you to hunt down specific monsters, each gives you a relative location but thats it. You still have to find it on your own, and sometimes monsters could only appear at certain times or during certain weather conditions.

I'm fine with that to an extent, but if it does get a bit annoying if you have a lot of vague quests where you just need to randomly waste time trying to find it :/

You can do that in Zelda actually. Go to the mission menu and select the mission you want to do next. 

Well, when you're just excluding every other example of similar systems because its not exactly like Breath of the Wild it becomes much easier to make it sound more special than it actually is. There have been dozens of games dating back to the 80's where side quests involve talking to someone and then trying to figure out how to do what they're asking for with no further clues all on your own. As many have said, a step by step guide through every single quest is a relatively new phenomena in video games.

The simple solution is to give players the option to turn off hand-holding quest objectives. In Deus Ex: Mankind Divided (I know, not really open world but it has massive hub areas so it's still relevant), the developers make it so that everything is in the levels to help you figure out how to get to an objective (signs, graffiti, eavesdropping on conversations between NPCs etc.). It has objective markers but you can turn them off in the options and on the hardest difficulty, turns off the map markers by default.

It's worth noting that this sort of game design does require extra thought and work by developers so players aren't blindly searching for their objective. Laziness might play a part in why developers would prefer to just give quest markers.

Both Skyrim and Fallout 4 had quests that would show a region but when you got there, the markers would disappear and you'd have to search on your own. Some of the Cappy quests in Nuka World were so frustrating that I had to look for videos.

Skyrim had quests that were started by picking up an object but with no location given. I had to look one of them up because having that item in my inventory was driving me crazy. I remember a quest where you could buy an item from a trader, though they had no idea where it was used, but you could also hear a rumor that showed you the location of the dungeon--you just had to put the two clues together yourself.

Both games also had many unmarked quests, where nothing shows up in your quest-log at all. You just stumble over them. I like those a lot, though I'm sure someone is going to tell me that Breath of the Wild invented them.

Games that mix the elements make the most sense. MOST quests should tell you where to go because, otherwise, it's kind of silly for quest-givers not to know the details of their problem.

I am going to go with a completely radical alternative solution.

Games shouldn't have side quests at all -- or if they exist, they should be done sparingly. Alternative branches that have a meaningful impact on the story, sure. But side quests almost always dilute the game and weaken the cohesiveness of the story. The best parts of the game are confined to the main story. Unless the side quests are of equal quality to the main story or they present a new view to the game's broader story, they shouldn't exist.

Personally, I vastly prefer optional challenges (akin to Shrines in Breath of the Wild or challenges in Gravity Rush, Grand Theft Auto, or Jak and Daxter) than side quests.

I somewhat agree, though many games use them to push players into exploring areas.  Some players go through an open world game and miss like 80% of the content.  I talk to people who "beat" a Fallout or Elder Scrolls game but have no clue about many of the most interesting locations.  This type of person seems to need a push.  Others have some kind of OCD thing going on where they want side quests so they can have boxes to tick off.  Even though I might not share those play-styles, they're still as valid as any other.

Personally, one of my favorite recent quests in a game was an unmarked quest in Fallout 4.  People who need a log entry would probably ignore it, but putting together all the pieces told a tragic story about a settlement that was slaughtered because a girl there stumbled over a secret.  I love that kind of things but, honestly, I bet most people never even picked it up.