GTA is probably not a good example to give me, because I consider every game in that series to be very shallow and honestly rather boring. The Witcher series has strong narrative depth because of its source material, but the gameplay itself has little more depth than any other action RPG. This does not mean that these are bad games, but they have been in large part successful because of very well executed illusion of choice and the mass market appeal of their stories. From a developer's point of view, this is not a bad thing; casual gamers are attracted to narrative-driven games and will generally buy the next instalment in a series if it continues the story (or, as is the case with GTA, promises a new but similar one), so it is easy to guarantee more sales volume.
There are absolutely games which are better off for their complexities. For example, let's take Street Fighter. Assuming you know nothing of the game, it uses one joystick and six buttons with the following layout (labeling joystick directions for later; 5 is "neutral" or no-input):
7 8 9
\ | / LP MP HP
4--5--6
/ | \ LK MK HK
1 2 3
If you want to execute a standing Light Punch, you'd input 5LP, for instance. Characters have special moves which require a combination of directions to be entered on the joystick before pressing a button, for example 236P for Ryu to throw a Hadouken or 623P for a Shoryuken (aka Dragon Punch). Others require more complicated codes, for example Zangief's Spinning Pile Driver ("SPD") requires a full circle motion, or 632147896+P, while his Super "Final Atomic Buster" requires two full circles or 63214789632147896+P. This is an obvious example of complexity - modern game controllers clearly have more than six buttons, so couldn't Ryu and Zangief have buttons for their special moves (to lower complexity) without harming the game? The answer is no. It turns out that the execution time requirement of these moves are a necessary part of the game balance. SPD for instance only has one frame (1/60th of a second) of start-up after the input, but the input requires 7 (6321478+P is a valid shortcut), so the total execution time of a perfect SPD is 8 frames. Making SPD one button and adding 7 frames to its start-up would completely change the way the move worked and make Zangief a much worse character; with the input as it is, the code can be during certain game states such as during "blockstun" frames (when a character blocks a move, they are briefly unable to act except to continue blocking, but inputs can be buffered during this time) or while one of his attacks is recovering to allow for an "instant" SPD when leaving those states. In this case, then, the mechanical complexity directly adds to the depth of the game by allowing the player to create situations which would not exist were that mechanical complexity removed.
Of course adding complexity does not necessarily make a game better or more fun (see: QWOP's reception) but the converse claim - that removing complexity necessarily makes a game better or more fun - is also fallacious.