I think a game is deep if it forces the player to make deep choices. A choice is deep if there isn’t a single clear right answer. A choice isn’t deep if there’s often one clear right answer, or if lots of things are qually good so you might as well act randomly.
Rock-paper-scissors is a good example of a game that, IMO, isn’t deep. The choice the player makes isn’t meaningful, because–absent external information about the other player, like “he’s hurt his hand, and can’t hold it out flat, so he can’t choose paper”–all your options are equally good. You just pick randomly and hope for the best. I know there are tournament players for rock-paper-scissors, but my understanding is that they add depth by studying the patterns of other players and trying to work out the psychological factors that go into one play or another. The depth there isn’t built into the game.
Super Turbo, by contrast, is deep, because the choices you make are meaningful. Say you’re playing Ryu. Will you walk up and throw? That gets pretty good damage, but not as much as comboing into super. Will you use a meaty attack and combo into super? That’s worth a lot more damage, but it’ll only work if the opponent thinks you’re going to throw; if not, he’ll block and you’ll just have reset the match (or, worse, wasted your super). Will you just block, anticipating a reversal? That gets the best damage of all if it works, but it’s only worth anything if the opponent thinks you’re not going to be blocking. In addition to thinking about what damage your choices give you, you also have to consider what you and your opponent have been doing in the past. If you’ve already pulled out the walkup-throw option twice, the opponent’s not likely to fall for it a third time–but he might be primed to throw out a jab to stop a throw attempt, and that makes him vulnerable to a meaty attack. Then again, your opponent knows you know…and so it goes. There isn’t a clear right answer, and random guessing isn’t as good as calculated decision making. You’re making deep decisions, and that makes for a deep game.
(Note that in Super Turbo, too, some of the depth comes from psychological factors, but it isn’t entirely coming from the players like it is in rock-paper-scissors.)
I’m tempted to say that “deep” and “meaningful” are the same, but I think “deep” captures the idea a little better. “Meaningful” is binary; a decision either is meaningful (i.e., not obvious and random guessing isn’t as good as calculated decision-making) or it isn’t. “Deep” is more granular; a decision can be more complex (and thus “deeper”) or less so.