Neverwinter Nights, although I guess that's more like BG and D:OS in terms of complexity.

I hear Wildermyth can be played co-op, too, haven't tried that one yet. Turn-based (rogue-like?) RPG, but maybe not quite as complex? It's praised for its unique storytelling approach.

Castle Crashers is a fun and comparatively simple co-op game in the beat-em-up genre, no idea if it would appeal to your wife though.

Maybe the Trine games (puzzle platformer)?

Also, Lara Croft and the Guardian of Light + Lara Croft and the Temple of Osiris (twin stick shooter + puzzles).

Gunfire Reborn and the Borderlands games might be too FPS focused, I guess?

Anotha vote for tha Trine games. Try'em.
https://www.gog.com/games?query=trine

May be
https://www.gog.com/game/project_zomboid


https://www.origin.com/usa/en-us/store/it-takes-two/it-takes-two
https://www.origin.com/usa/en-us/store/a-way-out/a-way-out

Indeed the Trine games are great for co-op like JackknifeJohnson said.

Other suggestions on Gog are:

- Aqua Kitty: Milk Mine Defender
- Pile Up! Box by Box
- Haven (maybe?)
- SpongeBob SquarePants? I'm not sure if Co-op here means two players at the same time or they alternate.
- Biped . Definitely looks great for Co-op
- Mighty Switch Force Collection

Those would be my primary choices. Yours may vary a little if your wife is more into action, puzzles, or even a good story. For example Stardew Valley works for the latter

https://www.gog.com/games?features=coop

Good gaming to the lovebirds.

Look again, he's NOT looking for FPSes

Project Eden

Commandos 2 (only the original)

Trine series

Hidden and Dangerous

Apart from those already mentioned (a big shout out to the Trine series in particular)

https://www.gog.com/en/game/satellite_reign
https://www.gog.com/en/game/system_shock_2
https://www.gog.com/en/game/sacred_gold (and possibly its sequel as well)

are three that I know of, though I'm not sure how easy it is so up in the case of System Shock 2.

https://www.gog.com/en/game/terraria of course as well, but I wouldn't call its campaign a story mode xP Phenomenal coop game though.

https://craftinglegends.itch.io/deathtrash

A extremely oddly named game. Seems to allow coop campaign play. Has great reviews on Steam

You might wish to buy it from Ich.io because Ich.io seems to be more community spirit, less business. You can even choose how much of purchase goes to the developer and how much to the site. And you can download it to multiple different computers as you like. It is on GoG too. Same price regardless of where you buy it from, $20 normally, $18 on sale.

Cat Quest 2 - https://www.gog.com/game/cat_quest_ii

The game is meant to be played co-op, two players on one PC that go on a quest together. There is no split screen. If you don't have someone to play with or don't have a gamepad, the game will give you an AI partner where you can swap between the cat hero and dog hero.

Secret of Mana (Super NES) comes close. Unfortunately, you only start with one character, so the start needs to be played solo, and there's one short part where you lose your companions, but the rest of the game can be played co-op.

Secret of Evermore (Super NES) also comes close, but only if you mod the game, which you can't easily do on the console (and you'd probably need to acquire an illegal copy to do this, unfortunately).

(I don't know about Trials of Mana (Super Famicom), but it's probably in the same situation of one of the other games mentioned above.)

Shovel Knight: Shovel of Hope, I believe, offers full co-op mode. (But not, say, the other Shovel Knight campaigns.)

Some shmuops offer co-op as well, including Tyrian 2000 and Crimzon Clover: World Ignition.

Note that, I believe, these games are all "couch co-op"; you play on a single copy of the game, on a single device, but with two controllers. (Tyrian 2000 may be the exception, but making network play might take a bit of work.)

Not an incredibly developed story but SWAT 4 here on Gog does allow for coop for its missions.

Amazing game to deepen relationship

Amazing game to ruin relationship