Some recommendations follow. First though, here's how I would think about this. What your wife will enjoy playing will depend on a variety of factors (theme, mechanics, play time, competitive intensity, etcetera). As you try different things, hopefully you'll get a feel for some of those factors. For example, my wife prefers historical, fantasy or modern settings of sci-fi, having kids skews us toward shorter play time, and she likes competition, but disengages when she's frequently way ahead or way behind. I like most strategy games (and hate most party games), but I've found I dislike Citadels because it is too easy for someone to fall far behind early, and it plays incredibly slowly as you add more players. You'll probably also notice that I link to boardgamegeek pretty frequently. It's a great resource for getting more info about a particular game before you buy it. Some games you can also try online to get a basic feel, for example on brettspielwelt or octgn
The first thing I would recommend is to try some Dominion expansions. The base game is actually fairly boring compared to Intrigue. There are some good questions in here about in which order to try the expansions, like this one. For a really close relative of Dominion, try Ascension. It is so similar I almost didn't mention it, but it has a few interesting differences, simpler here, more complicated there, and a very different theme.
I second the Android: Netrunner recommendation. There are some terminology hurdles, and I think my first 5 games with my bro-in-law we hadn't figured out the rules yet, but it bears a lot of similarity to Dominion in that it depends heavily on card text, and you can have a lot of diversity within the game framework because there are so many combinations to play with. I feel like in Dominion you play to build an awesome deck and then suddenly the game is over...in A:NR you build an awesome deck before the game starts, and then play with it. That setup bit is a bit heavy, though.
7 Wonders is a good option to try. It doesn't have quite the diversity of Dominion, and it plays much better with 3-7 people than with 2, but it's fast and fun. Not a lot of downtime per player. Also note: this is a tableau-building game, not a deck-building game.
Race for the Galaxy is another good one to try, and it plays very well with 2 people. This is another tableau-building game, but with a bit more variety (I think) going on than 7 Wonders, and it has a role-selection mechanic that adds a very cool layer of strategy. And it plays well (better than Dominion) with up to 6 people. If RFTG looks too sci-fi or too complicated, check out San Juan.
You should also check out Infiltration. It's by the same designer as Dominion, and similarly has a basic ruleset with components you randomly swap out between games. It has a little bit of Uncle Wiggily in it, but also some strategic elements. And 3 out of the 4 times I've played it the player who won did so with a last-minute hat trick strategy, which is quite exciting.
Cooperative games can be fun, but I think of them as risky business. Check this out. My wife and I have had good luck with Elder Sign, which gives individual players a good degree of autonomy.
The Ticket to Ride series (e.g.)is another good idea to check out.
