Industrial and/or spooky themes rock. Sadly, both were more or less covered with Moody Maze Marsh already, but neither was done in a way that was all that satisfying.
In general, I prefer "manmade place" themes (like Rusty Bucket Bay, Witchy World, Grunty Industries, Clanker's Cavern) and "genre" themes (Mad Monster Mansion, Gobi's Valley, Treasure Trove Cove) over "elemental" themes like "ice", "lava" (sorry Omega) and so on. A manmade place can have many different areas, and a genre can have many different aspects, but an element will always be that. Freezeezy Peak is a good example of an elemental theme (ice) being combined with a genre theme (christmas) to make sure the level has more variety. Glitterglaze Glacier has that little castle subtheme, but just like with Moodymaze Marsh, it's not developed enough to make the level feel like more than "lots of ice" to me.
So, a factory or plant would still be great (could effortlessly be combined with something like a lava subtheme). Or a spooky castle level, e.g. with a frankenstein-y lab. A junkyard level with toxic waste and sewers. And, to repeat what I wrote then, a run-down tourist trap at a grimy lake, with hotel, camping site and roach NPCs.