Add a difficulty setting separate from map selection. Doing so would greatly improve the replayability of the maps, as, unlike in gameworlds such as Ballrace or Minigolf, difficulty isn't (or, at least, doesn't have to be) tied to the level design. People of all skill levels and difficulty preferences would be able to enjoy all of the maps.
Also, change the difficulties around and add new ones. I think the current "easy" difficulty should become "very easy", "medium" the new "easy", "hard" the new "medium" and that a new "hard" difficulty should get added, along with "very hard" and "True Apocalypse" (or call it something else, like "extremely hard".. the point is, the names should be representative of the actual challenge the players will face when they select a difficulty).
The amount by which difficulty scales with more players should be increased as well, so that the difficulty stays the same no matter the number of players.
That is... if difficulties actually affect anything in the current version of the game. If they don't, I suggest they are made to. (because honestly, I don't think the layouts of the maps make a significant difference when it comes to difficulty)