Well, we got five different level types already:
Maze of Rooms
Hellish Caves
Maze
Arena
Hellish City
This is roughly in the order they can appear (Maze of Rooms is always on floor 2, cave/maze can be right after that, I've seen Arenas as early as floor 5, cities come right about there). Any of these level types prior to Hellgate, other than mazes, can come with random pools of water (early) or acid (late). After Hellgate, any level type including mazes can come with random pools of lava.
Enough background, though, we're all more interested in how hard they get. Early on, yes, mazes are a pain and likely the most hazardous type. As the enemy challenge level increases, however, Arenas and Hellish Caves definitely become more difficult, simply over the lack of reliable cover. Mazes at least have the benefit of providing cover, and its walls are destructible such that players can open up the area themselves. Dealing with the more vicious enemies in the game (Arachs, Viles, Mancubi, Revs) requires both offense and defense, and in Mazes you're lucky enough to be allowed these luxuries.
If you want to fix the amount of death caused by mazes, I suggest that the level type simply appear at a later time. It might be a good opportunity to introduce a new type altogether: I recall someone suggesting a warehouse, which could be simplified as big rooms (that is, doors between them) with mini-mazes filled with boxes that are easily blown away by shotgun fire. This would create the same capabilities one has later on with the Maze type, without the extra difficulty it causes in the early stages.