I really think the answer to this question is basically always "Use the 'First Game' kingdom as described in the rules for the base set." Yes, there are other equally great first kingdoms, but that one in particular is known and proven. I've never gone wrong with teaching new players that one: the cards are simple and fun, teach the core mechanics without branching into weird edge cases, and allow for a few different strategic avenues.
The only change I've ever made to that was swapping Militia out when I was teaching someone I didn't think would appreciate an attack that heavy. Militia isn't as brutal as Witch or complex as Bureaucrat, but it stings. Deck inspection attacks (e.g., Spy, Rabble, and Fortune Teller) would be decent substitutes for an attack-averse player.
+1 to favoring fun cards over strong cards, and teaching the mechanics of the game over strategy. Cards like Tribute, Counting House, and Adventurer are tons of fun to play out; it doesn't matter that their strategic uses are narrow. I still wouldn't use those in a first game, because I'd use the First Game as the first game, but they'd be great additions to games 2-4, say.