I may have to rethink my approach.
I just played a 3-player game with one relatively new player in which I randomized a kingdom with an app and then swiped away all of the broken cards or cards that required a lot of decision-making. No brutal attacks, and no big draw card that would make an engine too easy. I was basically left with a bunch of cards that are easy to play, but difficult to play well, and really no idea how I was going to do anything with it. I could see that a money strategy was going to be easy to pull off and probably win and I promised myself not to pursue it.
I described all of the various options in detail, pointed out the card interactions, the different roads to victory, the different ways the game could end. With the new player, we often told him literally how to play his cards to achieve different effects and what his choices were with a particular hand and the likely future consequences.
It had two or three terminals, including Bridge Troll and Artisan. The only splitter was the expensive but flexible Plaza. I pointed out that with a Bridge Troll on the table, Artisan can gain gold to hand, then topdeck a colliding terminal, which the new player used to great effect. We encouraged him to buy Forager early for thinning, then he spiked $5 early and bought the first and second Bridge Troll, Artisan, started Gold-gaining and got a big lead with three Provinces.
What was I doing? Well, being an experienced Dominion jerk, I guess. Once I got a good look at the kingdom and thought about it for a minute, a plan came together.
Open double-Forager. Silver for Economy, Forager and Bonfire to trash down to practically nothing. Bridge troll on first $5, get a second Bridge troll quickly, Forage the Silver to thin and make Forager better. Pick up an Artisan and sprinkle in a couple of Plazas. With gobs of buys and two Bridge Trolls in play routinely, piledrive Patricians and Vagrants while buying other good stuff, and with so many actions in play subsequently, buy discounted emporia by the handful for points and more economy. Buy Triumph a few times in the process for piles of points, trashing the Estates with Forager. Buy discounted distant lands by the handful, and/or gain them to hand with Artisan and play them immediately, or draw them (and leftover Triumph Estates) with Vagrants. After impossibly drawing deck twice in a kingdom with no draw, end the game with a flourish, piling out the last four $2 Plazas and a final Triumph, winning 30 to 18 to something. (Plaza/Vagrant/Patrician-Emporium. Didn't even get to the bottom of the Distant Lands pile.)
I really didn't think that was going to happen that fast or be that effective. I was just playing an engine out of pure reflex.
The inexperienced player (but experienced gamer) said, "Wow. That's a lot of moving parts. It's sure not Settlers of Catan!" Ok, so, mission accomplised, new player is impressed with the game's depth and complexity. Follows that with "I should have bought more Vagrants." What? No! It's a terrible card! It just happened to fit in precisely with my wonky Distant Lands strategy that kind of shouldn't have worked, and hey, free discounted stuff. The downside to doing weird, suboptimal things in order to give new players a fighting chance is that they then overvalue cards that you've bought and played optimally.
There's another way to play which I've used in the past, and I think it might be the best way to teach, but I just hate doing it, and it rubs me the wrong way and goes against the spirit of Dominion:
Play the same kingdom twice.
I know, right? Bleah! But seriously, try it. On the first play, do the correct thing and stomp the living snot out of the beginner. They will see what you do and will copy it. In fact, during the second playthrough, help them decide what to do during the play to copy your strategy. In that second game, do something different yourself. You will usually lose, but the new player has had a chance to try the correct strategy. You will sometimes win, illustrating to the new player that there are many roads to victory, but they won't think that the wonky one is the correct one (because when you played the first game, the primary strategy was probably clearly better.)
But I only do that if I can get the new player to commit to playing at least two kingdoms, because you have to play at least two to understand how deep and replayable it is. Four games is still reasonably quick.