One of my favorite games is “Nuclear Throne Together”, although it is quite hard, and more players make it much harder.
A current good and accessible one is “Vectronom”, a very stylized rhythm game where you play as cubes moving through levels morphing to electronic beats.
Mainstream games Rayman and Overcooked are also very good and fun and instantly accessible even to “non-gamers”.
Another one I discovered which is quite fun is “Hidden In Plain Sight”, where all players look like NPCs and most modes revolve around figuring out who is a player and who is CPU. It can be really intense because of the psychological terror.
“Lovers In A Dangerous Spacetime” is fun but gets tedious because of the huge levels.
Most of those those don’t have mich of a story though, except maybe Rayman. But that doesn’t detract from the games being fun.
Overcooked 2 is our current fave. Also Diablo 3 is a classic.
Why is it so hard to find story co-op games... always MMORPGs, RTSs, or sandbox games. Battleblock theater and pit people were fantastic co-op games.. and stuff like Halo's co-op campaign was great :-/