I always went for the new player playing the role of runner and the runner playing with an open hand. The game is pretty easy to pick up after a game or two, if the person you are teaching is already well versed in things like Magic, WoW, Yugioh or other card games.
First, I explain that the Corp goes first and take them through a typical first turn of the Corp, explaining why I am placing cards down in a certain way and what they may or may not be. I explain clicks and how they function, along with the possible actions that can be taken.
When it's their turn (I explain that there is a Mulligan rule, but skip over it as it is a tutorial) I walk them through their strategies and explain the cards in hand.
My tutorial decks are Haas Bioroid Vs. Shaper for simplicities sake. I only walk someone through a run when it is possible for them to perform one. For example I tend to leave either HQ or R&D open after my first turn to explain the run and the reason behind it before explaining ICE effects during a later turn.
Most I've taught tend to grasp the game after a few turns, maybe two games at most. I tend to have new players stick to runner for their first few games before having them play the corp. That way they grasp the role of the runner as much as possible and can then take the strategies they learned that way and apply that to defending themselves as the Corp.
The asymmetry can be tough. I usually use a small card reference that I made up that splits them down by card type. I explain 1 side at a time, beginning with the corporation. Operations first, then the other cards since they all go face down.
As far as decks go, I always use a very basic Weyland and very basic Kate deck to teach. I think they play the game in the most "traditional" fashion, with emphasis on keeping players out of forts and ice breaking to make access, with no traps.
After the player gets the gist of the game, I tell them about traps and play them against a modified haas-bioroid and criminals deck.
I've found it much easier to teach the game to someone who has previous with other CCGs / LCGs like e.g Magic.
I tend to start by explaining that everything revolves around agendas - the runners are trying to steal them and the corp is trying to score them to win. I show an agenda card and run through the text on it. I would then move on to explain ICE (used to protect these agendas) and demonstrate / talk through a few cards and then icebreakers as the natural follow-up.
I've found this works well for me in the past. Good luck !
I actually wrote a bit of a tutorial so my FLGS can teach other people. My recommendations:
1) Use very basic cards that have to do with money and runs. No traces, tags, or viruses; not even turn structure, central servers, damage or trash costs.
2) Explain the asymmetry by saying the Corp has all the secrets, making them a defensive role. The Runner has no secrets, making them aggressive. Segue into Agenda points and winning.
3) Explain that the Runner plays cards very traditionally - cards are played face up and clicks/costs are paid immediately. The Corp plays cards very differently though, in a two-step manner - they cost a click and go facedown first, and are later turned faceup and paid for. This is a good thing! If the Corp waits as long as possible to rez cards, it can keep its secrets and surprise the Runner. Notice how cards that are rezzed have black cost icons and Agendas have white cost icons.
4)Demonstrate Events/Operations by playing a Hedge Fund and a Sure Gamble. Set up a simple remote server with Wall of Static and Rototurret. Then walk the newbie through a basic run, showing them how runs are expensive for both sides.
This is enough to show the underlying structure of the game, and a little bit of what makes the game so interesting: how both sides marshal their forces that are spent during runs, and how the corp keeps the runner guessing. If you see that lightbulb turn on above the newbie's head, mention that there are several more things that make the game more interesting, like what the Runner does to central servers, damage and trashing assets/upgrades.
EDIT: If you can get your hands on a double-sided playmat, it'll help immensely. Something with labeled card areas and a click counter and the list of things to do with clicks.