The general notions that spring to mind are (a) play games which have a substantial element of luck to them (agreeing with those who already said this); and (b) play games which (i) you don’t know very well, and (ii) allow for a wide variety of strategic approaches (meaning you can try completely different things every game, and some of them will turn out to be rubbish, hence making you reasonably likely to lose some of the time).
I’m in a similar situation, and for whatever reasons Hansa Teutonica – a game with zero hidden information – was something we chanced upon which my other half truly enjoys, and which facilitates so many strategic approaches that every game tends to be a totally unique thing which could go either way. A wide variety of in-game options also means that, should you feel like doing so, you might choose to pursue an approach you’re not terribly confident in, as a form of handicap (not necessarily playing badly, but perhaps just playing with a variety of different strategies just to see what happens).
(If you did end up playing two-player Hansa Teutonica, make sure you’re using the revised two-player rules – these were released with the Britannia expansion, and the rules are freely available online.)
We also really like Hive, and I’m not sure if that particularly fits; but in my case, once my other half had properly gotten to grips with how the game works, I found that I was far from guaranteed to win. We’ve had a couple of really epic games of that (each winning one), which I was pretty thrilled about.