In a couple of places (G+, for one, and in an article I read elsewhere) people have talked about good "intro" games for kids. Basically, a starter RPG.
Me, the starter RPG I recommend is full-on GURPS. Why? Because if you join my group, I'm going to run it for you. It's not that hard, although you can make it so. With a GM running it, much of the complexity can happen behind the scenes. Video games work exactly this way - does it matter to me if the tank game I'm playing calculates cross-wind and reduces my accuracy if I just point, click, and it says if I hit or miss? Nope. It doesn't matter in an RPG if you roll a 9 and I say "you hit!" and that's the whole extent of your participation in the rules.
But, my answer for people who want to start an RPG without a teacher - say, you want to gift it to a kid and have it be essentially read-and-play out of the box, well, my opinion will be different. I'd probably go with GURPS Lite, but if it seemed like they really needed a pick-up-and-play game I might go with Labyrinth Lord (if "free" is what I want) or Basic D&D (if it doesn't matter). Here the issue is the book needs to tell them everything they need to know without reference to a teacher. They'll Google stuff anyway, but you want to ensure they don't actually have to do much besides figure out to start, and then start.
But except for very young kids, I don't think rules complexity is an issue. Even for learning to play. When I was 9, I was playing and running Basic D&D. I did need someone to show me how to play, and how to read a map key (sorry, I wasn't born reading maps), and confuse me by adding in AD&D rules to the mix without telling me they didn't mesh flawlessly. But I learned. By 10 I was running AD&D. By 13 I was running GURPS and Rolemaster (I did get one chargen issue wrong in it, though) and other games.
I can't possibly be unusual in this respect. I don't think kids need things simplified for them. Very young kids, yes, I think it helps to simplify the larger game-world concepts and story elements (killing a PC and doing an endzone dance is funny when you're all 40, not so much when you're 7 and dad does it to you.) But rules? I don't think it's necessary.
So yeah, starter RPG? I'd hand someone GURPS in a second, and I'd run it (and frequently have run it) for people brand new to RPGs. It's not necessary to shield new players from potential complexity, because the obstacle is "Is it fun?" and not "Does it have a lot of rules?" At least to me it isn't.