I would have tied Azeroth to the Shadowlands characters and created more lore that felt connected to Azeroth.
So, 1 idea could be - the big names who we meet like Vashj, Kael’thas, Draka, Alexandros, Uther etc - have them be given “something” that allows them to travel back to Azeroth, for a brief amount of time to places that mean something.
So, for example.
With Vashj, Necrolords players would go back to both the Ruins of Zin-Azshari, Serpentshrine Cavern and the Ruins of Vashj’ir (Quel’Dormir Gardens.) We’d hear more about Vashj’s take on how things went, but also hear more about her mother, Lestheria Vashj, Quel’Dormir’s High Priestess, Siralen and Vashj’ir High Ranger, Valarian.
Some might cross-locate such as Uther and Alexandros; but their stories would take different routes. For example Alexandros’ story would relate more to the Scarlet Crusade and hold more involvement with Northrend, whereas Uther’s story would be more about Lordaeron and reflections of Arthas.
The only requirement would be that you were level 60.
I know this might be quite short, and doesn’t cover the widespread issues surrounding the story, but it might help connect some dots.