I think destruction in certain areas of the game, as stated a few posts above with the example of breaking through a wall of the ONI Building, would work really well and definitely add a lot of realism, as well as the possibility of there being more choices for the player.
With the covenant on the other side of the door, do you fight your way through them, or blow down the wall a few rooms away and flank them?
I think it would be a nice addition to have destructible scenery also, not all of it, but places where you can take cover.
For example, you could be hiding behind some sort of barrier or column, and a kamikaze Grunt could run directly at you, destroying your cover and exposing you to the Elites waiting further in the distance.
Overall, I think it would be a great idea. One thing that I've always found lacking in Halo was the destruction. Not "for the luls" but because of the added realism