A cooperative puzzle game could be pretty awesome, like having each player work together to solve it. Perhaps give each player a certain "task" that only they can do that is paradigm to solving the puzzle, but they can't do it all on their own, thus they require the "tasks" of the others to complete it.
Like let's say that the puzzle is to build an irrigation system in a block grid that feeds to many points.
-1 player controls gravity and can switch between water in a grid flowing up and down and hills
-1 player digs ditchs for the water to travel into
-1 player builds aqueducts for water to flow up
basically certain obstacles require different types of paths for the water to travel, and you can only have 1 type of object in that grid at a time. Thus all 3 tasks feed into each other to cooperatively devises a way that makes water flow correctly with the least resources used.