I'm not sure if anyone is familiar with the Red Faction games, but they were two FPS games on the PS2, and were well recieved for their destructable enviroments.

If you have Xbox Live, go try out the Demo for Red Faction: Guerrila.  The destruction engine is amazing to see in action.  Albeit, I'm still having some trouble with the game's cover system, I still think that It looks very promising.