Mario 3 is shallow now?
Wtf are you guys yakking about? Just say what you want to say without twisting each others' words around in an effort to make yourself look smarter.
You're both mixing around two different scales:
1. Shallow to Deep
2. Simple to Complex
and even with all this mixing around I have yet to understand your points.
A simple game can be shallow... such as Katamari. You basically roll... and then you roll. Once you get the hang of that, there's not much to improve on.
A simple game can be deep. Mario 3 is an example of this, for each level can be played at largely varying skill levels, with different results. Soulcalibur is another example. There are no complex weak, strong, fierce, punch, etc. buttons. There are only attack TYPES: horizontal, vertical, kick -- very simple. But the depth that the combinations allow is tremendous.
A complex game can be shallow. Most FPSs are an example of this. They are very complicated to control, but the general case is that once you get good at aiming/strafing, you're good at the game. (Notice I said most.)
A complex game can be deep. I can't think of too many examples of this outside of some fighting games... maybe games like 2D Castlevanias.
You both seem to agree on this (not on the examples, but on the concepts) so stop your jibber-jabbering.
EDIT: I am sad Gitaroo-Man is not on the list, but I can't say I was hopeful.