On reread, found a new one that I think would be great for this thread.
In ACOK, Arya (hiding as Nan) asks Bolton if he was going to take her with him once he leaves Harrenhall. He refuses.
What changes if Roose Bolton took Arya with him once he left Harrenhall? Or if he just said yes.
Gendry and Hot Pie might be in trouble or not, because the cook and Ben Blackthumb survived both Vargo Hoat and Gregor Clegane.
But it is Arya's story that changes a lot. Arya is right there at the Harrenhall while Roose is plotting with Walder Frey in preparations for the Red Wedding. She sees every one of those preparations, because she works as a messenger for Bolton and not just a cup-bearer. If she is able to sneak a paragraph into one of the messages to Rob and Catelyn, Catelyn never sets Jaime free. Which means Karstarks are still on Rob's side, Jaime has never lost his hand and Arya is right there at The Twins laters, in Bolton's livery and meets with her family before the wedding.
The wedding is no longer red. Rob apologizes to Walder Frey and there is a double wedding, Edmure marries Roslyn and Arya marries Elmar Frey (Walder Frey's youngest son,as originally planned). On the other hand, Arya never joins Faceless Men or meets the Hound, so Hound never gets his redemption.