Dark Souls would be fun though you can only have 3 people playing co-op. Also, I think it's pretty hard to get everyone on the same game, haven't tried it in a while though.
For the catacombs, get the light spell and a divine club, that part is easy as hell if you have both of those things.
Wipeout HD has been pretty fun every time I've played it with others here, though we did run into some problems last time we tried playing together. There's also MGS Peace Walker though I don't know how many own it and on what platforms.
In terms of PC, I have the Dawn of War games, Space Marine and Magicka, I think multiplayer would be fun in those games though I've only played Magicka in local co-op.