Recently, I got and have been playing Patrician III, which can be played in multiplayer cooperatively. A bit different from your usual choices, it seems - it is a trading game, set in Northern Europe in the heyday of the Hanseatic League. I think this short review gets across the idea of the game pretty well. I would add that due to the open-ended nature of the game, it is very possible to cooperatively work towards the goals you have set yourself in multiplayer.

I have no idea if you two would like this kind of game at all, but if you think it might be interesting, a quick googling revealed time-limited (but apparently, feature-complete) trial versions available here and here.

Links to a couple of other reviews:

Gamespot
IGN