I'm simply going to suggest a labyrinth themed variation of arenas, a new monster: The minotaur.
Labyrinth is pretty simple, design it with high walls like a maze, the mini map becomes hazy, and perhaps there are few light sources and it proves more difficult to navigate. It would encourage more multi-player( I myself prefer to solo only, because I'm greedy and find I am quite capable of charging through levels myself =P) because it would simplify finding the correct course with more players navigating the many channels.
A simple theme that comes to mine is a Greek theme. Think olive branch leaf designed helms, 5* swords called Brutus and Cesar, Toga upgrades based on the cloaks, and so on and so forth. For all you haters, think about the rapiers and rose regalia that have an obvious theme to them. Maybe delve into Greek mythology? Maybe not.