I can recommend Pandemic, especially, trendy nowadays :) It is not deduction, but more strategic. In this game you collaborate with the other player to win against the game, instead of playing against each other. If you play just two, every game you might need to modify you strategy, so it is different and is not boring :)