FFG puts out demo decks that stores can order from them. I'm not sure how much they cost, but I'm given to understand that it's not a ton.
I'd advise against making the decks overly complex in the name of showing off different archetypes. All that's going to do is drive up the rules overhead you'll be exposing new players to. The demo decks, for instance, have no tracing ice whatsoever and go so far as to omit Kate's link value from her demo ID.
If you're building your own demo decks, I'd try to keep the cards mostly limited to the Core Set. I wouldn't want new players to see something cool in a demo I ran, then be disappointed after buying the Core Set because they couldn't do that thing. (So no Keyhole, for instance.)
I think I'd want to build a Runner deck that's more traditional, like 'big rig' Shaper, and then a Runner deck that's got more tricks, like maybe Criminal with Parasites -- something that shows off what you can get up to when you start mixing and matching faction strengths. Similarly, I'd want a traditional/glacier Corp deck (so HB?), and then a flatline deck. I'd try to avoid SEA Source Scorch, as experience has shown me this can be a big turn-off or negative play experience for new players. Maybe Jinteki but sneak in some Ghost Branches and a couple Scorched Earths?
Starting with the tutorial videos is a great idea, by the way! Guaranteed to attract attention and a useful teaching tool.