Looking it from that perspective, Mario will be considered much less complex, because the AI is poor in comparison. I think the level design is what makes mario challenging, and not the enemies. For example, New Super Mario Bros. 2 has a very hard DLC from what I saw, and it takes real skill to complete it. Though the enemies are simple, their placement and the speed required, as well as the availability of platform make it challenging to the core.

It all depends on what is our yardstick. But in the end, if challenge is the aspect we're measuring, AI is only one metric by which we can evaluate it.

Has it been mentioned already? Valkyria Chronicles, my favourite game of the generation to date, and the game for which I bought the PS3.

Fast cars: Nope slow tanks

sex scenes: Nope, but genuine love and affection

unnecessary/unrealistic profanity: Nope, very clean dialogue

super soldiers: Nope, a rag tag group of weekend warriors with a head in the clouds biologist to lead them. Although Rosie does become pretty kick arse once she's leveled up a bit, and if you've played the DLC that gives her Selvaria's weapon. Oh and Alicia turning into a Valkyria, but that's at the end and it doesn't play a major role in the battles.

lone survivor of the zombie apocalypse: nope, no zombies.

One minor concession to the sex thing: there are the occasional up-skirt shots when female soldiers are lying down hiding from the enemy in long grass, you can see their underwear. But that's not a sex scene per se.