A simple plot can be deep enough, I saw this with Dragon Quest VIII and Ys: Seven. The plot there is simple, but the theme in both games is strong enough, to tell a story about something. In the case of Ys: Seven the devs also let some things open for interpretation in not telling it all. The Ys-games in general are very good at that.
Divinity: Original Sin 2 is in my book also a good example for a deep story, that also combines its plot through one big theme: power. It's about power, how to use it, how it can consume you and how unfit you maybe are to use it. Every important character reflects that and it is implemented in the game. I really think if you can implement your theme in the game, you can also compensate for pacing issues (the second act in D:OS2 was too big and you could see that the third act wasn't nearly finished in the original version).
Complexity is nice, but I don't think there's nothing wrong about a simple premise. The plot of Dragon Age: Origins could have been nice, if it didn't stop after Ostagar. My sisters and me were baffled when Wynne told us, that we were wandering around for a whole year, because it didn't feel like we achieved something. A good story has to give the player the feeling of progression. Doesn't have to be a big cinematic, an interesting document or a dialogue, something that gives you the feeling of getting stuff done, are enough.
I also think that it is important, that the player gets the feeling of progressingv through gameplay. My biggest problem with the newer Final Fantasy - games is, that the story and the gameplay feel like two different creatures. Best example XIII, the character Hope: in the game he's a whiny little coward, but in gameplay he kills legion of monsters with his boomerang, without breaking a sweat. I also think, that you have to do the beginning and the ending first, so they become connected. You can cut stuff out in the middle-part, as long as the ending feels good. For example Two Worlds II: started strong, lost steam after the university-setting and didn't make any sense in the end. You can really see, where they hadn't any money anymore. But the devs could tell complete stories, they showed that with the addon later.