I think that indeed, the theme decks are the best way to start, because the way the Trainer engines are set up, and having 1 of the "main" Pokemon, it is just screaming to get 2 of the same theme deck. Yes, you'll have 8 of some of the commons, but I think it's a better way than just using random cards.
For non-theme decks, I think it's important to make it simple enough for a new person to play, but not so weak that it can't win at all against even the theme decks. A balanced amount of Pokemon/Energy/Trainers can help, and the newer sets seem to do a better job of having common/uncommon cards that are viable for play. Not like in the EX series when most commons and uncommons were really bad, and even some rares/holos were horrible.