I find it really cool that the "Classic" Sonic games essentially had the same story as Adventure. From Sonic 2 they begin referencing the Chaos story in vague terms, and over the next few games, it gets more explicit until you see the whole thing in flashbacks in Adventure. I know some people like to keep it simple and don't enjoy when Sonic is dealing with all sorts of crazy cosmic gods and stuff, but I love it. As far as I'm concerned, the games from Adventure to 2006 were pretty close in most regards, including story, to Classic Sonic, which I enjoy (though I didn't really enjoy the story as much until later when I found out about the Japanese manuals being so different). They generally managed to feel like translations of the old games' style, but with more advanced tech that allowed things like voice acting and FMVs (plus being in 3D and all that other non-story stuff). Of course, after 2006 was a complete disaster, they kind of threw the baby out with the bathwater, and Modern Sonic, I think, is a completely different beast. I enjoy it, but it's not really the same in most regards. That said, I really appreciated that Unleashed gave Sonic more of a personality than he had in any other game. The plot there was a little lighter (in depth of content, not tone), but not a lot, and that's not really a bad thing anyway, but the characterization of Sonic was much stronger, whereas in other games basically all the characters except for Sonic got fairly strong characterization, but Sonic is essentially a static character. That's fine, I don't mind that, but Unleashed found a way to make him still feel like Sonic while also making him have some more complex emotions and feel like a character with more depth.
Then Colors and Generations had almost no story. They were alright games, but I do like when they try with the stories. I don't think story is necessary, it should never be prioritized over things like gameplay, but it's still nice. I hear Lost World is better in this regard, but I haven't had the chance to play it yet, so I can't comment on it.
Ideally, I'd want something with the general tone and feel of Unleashed, but with the use of continuity seen from Sonic 2/CD-2006 (each game there really does reference and build off the previous one, with CD and Adventure 2 being the exceptions that only refer lightly to the game before them). Modern Sonic at least has fairly good dialogue, though, not as cringe worthy as some of the other games in the series, so if we can keep that quality of dialogue but mix it with what I've described above, I think that would be ideal.
Incidentally, Ian Flynn does a pretty good job at reaching what I'm talking about, especially after the Super Genesis Wave, AKA legal issues, forced him to let go of most of the comic's original characters and concepts, which were really just dragging him down for years. If they just let him write the games, I'd be one happy camper. The current Shadow Arc in Sonic Universe is exactly what I want out of stories in this series. Just do more like that.
Also, since people have been talking about Shadow, I liked that he actually had a character arc. Sure, I get that people didn't like how angsty he was at first, but he solves that in his solo game, and in 2006 you're essentially seeing the epilogue to his story (especially as you look into the future in it). I thought his story in there was neat and his characterization was exactly what I would want to see out of him in the future. But then he hasn't really shown up a whole lot since then, so we haven't gotten to see him like that again.