How about a mode with very large, randomly generated maps where you have to locate something, such as treasure or a missing person. Defeating enemies gives you clues or data until eventually you have pieced together the coordinates to your goal, at which point you're faced with a boss. There are many kinds of randomly placed things you may find along the way, such as trader npcs with helpful items or buffs.