It's hard, because I think quality of the story is so much more important than complexity. Crono Trigger was overly complex, but it was far too good a game and a story for me to hold that against it. I'm a sucker for snes rpg's; I'd put Earthbound as a just right example.

I've lately become a little addicted to Sunless Sea, and it's almost entirely the story/atmosphere. Rich, weird, complicated world, but you get the iceberg effect where you're just experiencing brief snippets of what could be game stories of their own. I think too simplistic is when the world is flat, too complex is when the world is intricate and you learn all the intricacies, and just right is when you feel like this is a fully developed universe that you're tasting from.

Suikoden is always right to me. Final Fantasy VII is incredibly convoluted, which is probably why I never finished it. Halflife is one of the few FPS that has an interesting storyline/arc, and Fallout is in there somewhere. The Fable series is just about right for me as well. It is a slippery slope when one is talking about things like RPG and JRPG because there is the tendency to either go too little with the story or too much, where you get something totally overblown. FPS often tend toward too little story. So it just depends on the game really. It sounds like the game Destiny (which I have not played) has a good amount of story and a lot of lore, but story and lore are only great if people are interested in that story and lore. So as writers, we have to not only write the story, but write a story that people can actually be interested in.