So I'll probably bookmark this post as an info one about why the orcs are how they are.
Partly its definitely due to bad writing. Blizzard do some stuff well, but in general they aren't able to make the setting sufficiently cohesive to stand up to scrutiny, they focus far more on what's basically soap opera drama than they do on the sort of meaningful historical or at least fantastical authenticity that I think a lot of people want. As such, yes the orcs are genocidal etc because of bad writing, but I'll try and provide an explanation below for why this might be 'in universe'. Firstly, to address
Warcraft is one of the very few fantasy franchises where orcs are put in a positive light. This is still true after two games with the traditional bloodthirsty interpretation.
To give Blizzard the credit they deserve, since Warcraft II they've given the orcs a far more interesting history, just like they moved the Alliance away from the explicitly Christian iconography and terminology. The Warcraft Orcs are a legitimately interesting culture with their own history and customs, up there with the Orsimer from TES or the Orks from Warhammer. Orcs are frequently portrayed in a positive light, and although some are evil they're portrayed as a legitimate culture and people not just a mob race.
I'll structure the rest of the answer around three points, the ability of cultures to change, to self-reflect, and geopolitical considerations.
short period of time for any form of cultural change to occur
The Orcs went from being a fractious and combative culture hiding from larger and stronger opponents on Draenor (Arrakoa, Ogres, Gronn, Draenei), to a decentralised martial empire under Blackhand's Horde. In both cases the Orcs valued strength above all, which usually meant martial strength, but sometimes meant rogue type stuff or magical strength. Due to external pressures they were and are very traditional, probably because clans who tried to experiment weren't very successful and were destroyed. Anything 'weak' including half-breeds, disability or gentleness was looked down on, for example Gul'dan being exiled because he was disabled (looking at his art he has a hunched back and seems to have something going on with his arms).
This culture of valuing (martial) strength is pushed forward into the classic WoW period, but in general the Old Horde (that is the Orcs mainly) never really reach the stage where they could reasonably be called a state. There's no bureaucracy or professional military, taxation or similar to allow for other forms of power to develop such as institutional or bureaucratic power. As such the 'best', fastest and most sure way of becoming more powerful is through combat, battle and warfare, with a couple of side paths in magic etc.
Then Thrall turns up. Thrall is educated by humans, and then gets a very edited history of orcs and orcish culture from the Frostwolves and from Orgrim Doomhammer, neither of which presumably mentioned the whole 'paving a road using childrens bones' thing. As such Thrall fails to understand a couple of things. Firstly, he tries to map human culture onto the Orcs. This is partly successful because he specialises the clans more than Blackhand did, having the Shattered Hand as a police force and spies, using the Warsong as a military unit, using the Burning Blade as the demon police etc. He also tries to insert his supporters into positions of power, and changes some customs like (poorly) instituting gender equality. However, he never really understands how clans work, the Burning Blade say demon worshippers and there's no institutional inertia. When Garrosh turns up Thrall loses control of the Warsong because they answer to their chief now, just like a king is only able to control their direct vassals, not their vassals vassals.
Thrall isn't really ever taught how Orcish culture works by Drek'thar or Doomhammer, and is instead given a sort of edited version of events, missing out any of the dishonour and so on. He surrounds himself with unrepresentative orcs such as from the Blackrock or Frostwolf clans who clearly aren't able to or have no interest in changing stuff. As such Thrall doesn't really care to confront the Orcs about their past, he just assumes that they were all tricked by Gul'dan. This isn't true, for example when Grom drinks demon blood for the second time he says 'I need this to defeat Cenarius', which wasn't Grom's job, he was meant to get lumber and establish a forward base. However, due to the orcish culture because he's been opposed Grom thinking he 'needs' to be stronger regardless of the source.
Furthermore, there's not really an impetus for Thrall to do so. The orcs aren't doing any genocide at the moment (apart from the Quillboar but no one cares about them) and I'm not even sure he could do anything about them even if he wanted do given as we've established the Horde isn't a proper state, its a patchwork framework of unclear political and constitutional settlements because its development has been disrupted frequently. In the Classic period at least the Horde is beset by enemies and Thrall would have no interest in an internal fight which might endanger his position.
How might this be changed? How might you specifically change it if you wanted to? For one, there has to be a change to how Orcs acquire honour and glory, and progress in society. I'll bring the example of Star Wars in here, where a similar culture, the Mandalorians, has developed from a warlike culture to a bounty-hunting one, using their skills but doing so in a way that's acceptable and even praised by the rest of galactic society. The Horde need resources, specifically things like lumber and food. They get this by pushing into the lands around them, but they could also get it through trading. Now what do they have to trade? Primarily martial ability. The Orcs might become a mercenary state, exchanging soldiers for resources. This would create peace through interdependency between the Alliance and Horde, and would actually resolve some of the problems. It wouldn't necessarily deal with the genocidal impulses the Horde has due to culture, but it would give a release valve, and it would also allow for the greater development of different classes in Orcish society and means of advancement rather than just soldiering.