Speaking as someone who has only played a couple of games (really only one, the first was poorly timed and I was out of town).
Let me be honest: If you made me play a game as a newbie WITH another person I would flatly refuse and never touch this site ever, ever, ever. We play games to play them, not be led individually around while someone else does. It's a good way to decrease new player buy-in which is essential to gaining repeat customers. And it's a terrible way to "learn" how to play a game.
It is difficult as a new player, particularly in a game that very much has unspoken but changing standards. That's a lot for a new player to figure out very, very quickly (because, and correct me if I'm wrong, the early day... heck HOURS of the game are incredibly important).
I think games geared more toward new players would be ones that gave more advantages to keeping people on your tribe who are good at challenges. This gives more structure to a game which can help newbies figure out the other "softer" parts more easily and at a slower pace.