I think originality ended with Legion, story-wise. What would be something completely different?
What if we awakened on an alien spacecraft, where aggro was based on line of sight instead of proximity? We would constantly have to sneak carefully, finding objects to hide behind as bands of vicious aliens roamed around.
And there would be no quest-givers explaining everything one needed to do to fix the problem: there would just be mysterious puzzles to solve.
Another idea is about surviving nerubians wanting to expand their domain, recreate the glory days of the empire by burrowing under the other continents, causing a capital city or two to collapse into a cavern, creating a topsy-turvy place covered in webs to crawl through-no flying because there’ll be sticky webs everywhere so one can walk on walls and ceilings. And the nerubians go real dark with a new religious revival and do unspeakable things to surface dwellers. I don’t think Blizz has explored body horror that well.