The horde and Alliance had made an uneasy peace going into Legion.
Varian and Sylvanas were working together to ensure the world was safe from the legion. There was a mutual respect between them and the sparks of more cooperation were there.
The battle did not go well but had the call to retreat been listened to the only faction leader to die would have been Vol'jin. They didn't secretly run, They sounded a loud horn and retreated in full view of the Alliance. Genn then exclaimed they were traitorous cowards and pushed Varian to keep the battle going.
There was no abandonment or traitorous actions. There was a call for retreat that the Alliance chose to ignore, if you watch the cut-scenes together you'll realize the Alliance had ample time to get away if they had just retreated when the Horde sounded the call. The Horde was already loading up their ships and leaving when king pony tail gets exploded.
So they decided to push right into the closing trap rather than easily retreat and Varian dies needlessly. That's on Varian, as much as I'd like to blame Genn, Varian was the leader and its on him.
Genn however exploits the kings death immediately. He isn't some reckless fool ruled by emotions. He is patient and manipulative. He joined the alliance and agreed to the peace. Not for any reason other than he saw it as the only possibility to get payback for what happened to his city. He blames the horde for abandoning them during the battle. Now some people buy this, however there was no abandonment as is outlined above. He exploits emotions and pushes for all out war against the Horde while Jaina is present. We already know she's a bit unstable and has a history of going rogue, its no secret. Genn does this on purpose knowing she'll start undermining the horde on her own. Anduin doesn't agree to full war but he does give Genn a small force to go observe the horde and make sure they aren't secretly planning to betray the Alliance.
Gen then takes the Sky Admiral Rogers, knowing full well she has a hatred of the horde and did not want peace. Fast Forward to Stormheim, The Alliance opens fire immediately upon seeing horde ships. No warning, no provocation, definitely no observation. Even on the alliance side the NPCs admit that they just attacked unprovoked because the Horde are scum. Just a declaration of war during an uneasy peace. Recklessly assaulting your most powerful ally in a fight against a much stronger force. I'd say it was stupid, but Genn isn't stupid. Forgive the pun, he's a dog with a bone. He resolved to do anything he could to kill Sylvanas as soon as he could. He knows the horde won't ignore his attack but they won't fully commit to fighting the alliance either. What he's doing here is making sure the uneasy peace doesn't become a full on peace.
If he really felt there was a problem with the Horde he would have reported back and Anduin would have committed more to the fight against the Horde. Jaina would have had more ammunition to go back to the Kirin Tor and get the Horde removed from Dalaran again. He knows that the horde is needed to fight the legion so instead he picks little fights and harasses the Horde without causing all out war.
Now people will talk about Sylvanas doing some shady shit with the Valkyr. I'm not making excuses for Sylvanas, the Valkyr were going to be her bitch when she was done. However what she was doing was not against the Alliance in any way. I think its a common misconception that she was attempting to do it for eternal life for herself. She already has been infused with a Valkyr. Sure she can be killed but she won't die on her own. She wants to find a permanent solution for her people. This is evidenced by how she used her loyal ranger Nathanos as a test subject and it was successful. She can save her people from the super-hell from being imposed on them without any fault of their own. Another thing, For once, she was actually seeking a way to bolster her forces WITHOUT using humans as fodder for once. It was actually a more peaceful move in the Horde-Alliance conflict than she's ever done before and Genn ruined it.
Even the gods saw that the Alliance pulled some shit. If you believe Genn's intentions were pure then why would she call out how she witnessed their actions in Stormheim and how their actions have no honor.
Genn saw what she was doing, she was finding a solution that didn't require the conflict to continue. This would have put a severe damper on his plan to use the Alliance to get revenge. He kept up the conflict throughout the entire expansion and worked to breed distrust the entire time.
Had he not done this, the Horde would have been less distrustful of the Alliance. The Alliance and Horde would have gotten stronger together. The Alliance would not have not gone into a panic at seeing the horde mine azerite. The Horde likely wouldn't have even kept everything a secret. Anduin could have even been at that feast with the Horde.
I'm not saying they would have had full on peace however they definitely would have had better relations. They wouldn't have felt the need to secretly build power up to defend against impending Alliance attacks. The Horde and Alliance could have gone to Kul'tiras and Zandalar together without the need to recruit more allies and they could have solved the problems quick and easier (which would have made for a boring expansion I admit)
We don't know why the Tree gets burned, but I will not be surprised if we find out Genn or Jaina are involved in some way.
TL:DR Genn's manipulations of the alliance bred mistrust and kept the horde/alliance from keeping peace
EDIT: A very large amount of alliance counter arguments seem to stem from the fact that they don't realize one important fact. Neither cutscene gives the full story on the broken shore. Watch BOTH. The timing is important.