The more exotic levels generate about 5000 triangles, which is fairly reasonable.
Now I need to do battle with the physically impossible levels DOOM creates...
In DOOM, skies and floors are actually marked as the special texture SKY_1. However, rather than drawing it using the normal mapping, it's drawn fixed to the background.
I'm currently just drawing a sky cylinder, and not drawing ceilings where the sky texture would normally be. I need to find some way of masking out the buildings that shouldn't be visible.