There's been a dearth of good strategy games, let alone story centric, so I'm not sure if there's much to add. The only recent game that stands out to me is Nobunaga's Ambition: Sphere of Influence, which looks quite good but I haven't played it yet, since I'm holding out hope for a GoG release. There's also some upcoming games that might be good (That Which Sleeps, Six Ages), but that's still some ways off.
As far as older games go, the best ones have pretty much been named (with Myth 1+2, SMAC and Sacrifice at the top). There's still some I'd recommend to try out, such Heroes Chronicles, which is a series of scenario packs for HoMM 3 telling the story of Tarnum. It's not an especially challenging game and the story isn't spectacular, but it does have charm to it and Tarnum is a good lead. You can now also easily get them all in a single bundle, rather than having to pay full-price for each of them. Keep in mind that each game is self-contained, but the ultimate conclusion takes place in HoMM 4.
Then there's Domionion 3 and 4, which don't have a storyline to follow but do stand out because of how great the lore is (because it's grounded in real mythology).
Tone Rebellion has a story that is woven into the atmosphere and that you uncover as you explore the different realms and find artefacts, but it's more suggestive and doesn't follow a clear narrative like other games do. My personal favourite, but not for everyone.
Age of Mythology is also all-around solid, with a more cohesive story-arc than the sequel, Age of Empires III.