When teaching a first game, I use a tablet randomizer app (Jack of all Dominion. Silly name, great randomizer.) I set up the rules to require at least one +buy, at least one village, at least one terminal draw, at least one trasher, and at least one duration. I blacklist cursers.
Then I swipe away any cards that will either make the game miserable, introduce too many choices, or is game-warpingly good in a way that makes everything else irrelevant. Complex cards with too much text go away, like Count or Native Village. Lots of different mechanics are fine. I may or may not include Events depending on how sharp the players are.
But because I also like to play, I give myself a bit of a challenge. Because I know that new players are always going to buy too many actions, I try to build a kingdom that isn't a particularly good engine, one where BMX could win, then I play an engine anyway just for practice. So I'll swipe away Wharf but keep Dungeon. Swipe away Smithy but keep Courtyard. Swipe away Goons but keep Monument. It also keeps the turns shorter in multi-player.
For a second game, I'll re-randomize with no duplicates (but Duplicates are ok) and I'll leave some of the power cards in, but still get rid of cards that are too complex. I find this approach helps really introduce the game. The rules, the power variance, and the immense variety.
Here's the reality: Non-gamers or occasional gamers are never going to like it, no matter how simple you make it. Trust me, I've tried. Not happening. Casual gamers (even old-school fans of classics like Monopoly and Scrabble) will usually like it, even with a complicated kingdom. Hardcore gamers will be turned off if you oversimplify, so hedge your bets.