So, I introduced Dominion at a board game night yesterday. 4 players including me. One had already played Dominion, but the other two never did, but have played deck builders before (in fact, we had played Legendary just before). The idea was just to teach them the game so that if they were interested, we could all play Dominion for real next time we got together.
Due to their experience with decknbuilders, they were expecting a bit more from the learning experience that just the base cards and a single action card like Smithy. So, we started the game with Smithy, Village, and Market. I chose those cards because they are pure vanilla cards that showcase all the main vanilla effects and how they can influence your turns. They were actually quite disappointed at how useless the Estates were, but it was good to see them catch on to the drawback of green cards almost immediately (in fact they were hesitant to buy Provinces throughout the game, but of course you ultimately need VP to win).
A few turns in, I added Cellar on request to see more cards. A few turns after that, I introduced Militia. The player that had already played Dominion wanted me to show the defense card to Militia, and like a troll I introduced Library based on some of the discussion in this thread. I did add Moat too, but Library is nice because it shows the perils of dead draw by providing a solution to it (there was a lot of dead draw going on in our game). But man, explaining how Library actually works is a pain. It's the most confusing card in the Base set. I eventually added Remodel too (turn those Golds into Provinces?). As the game was coming to a close, I showed Throne Room to satisfy their desire for a wow factor.
We never finished the game, as some players needed leave for home. The game seemed to be well received, especially after showing Throne Room. It was the weirdest and funniest game of Dominion I ever played just because of how I ended up just trickling cards into the game. I wouldn't recommend teaching the game like this to players new to deck building or casual players in general, but that's how it played out for me.