Murloc: have a phase where the boss is submerged, and throws some dodgeable projectiles, and a way to force the boss to surface (his dorsal fin sticks out of the water and can be targeted, drop boulders in the water, etc.)
Fire boss:
Firewall: The boss channels a wall of fire that moves in a circle around his body. The more damage he's taken, the more walls there are.
Magma Chamber: If the boss fight is near an active volcano. Any ground-damaging moves (Thunder Clap, War Stomp, Shockwave etc.) cause a Flame Strike at the spell's location.
Ice boss:
Icicle: Huge icicles fall from above, remaining on the battlefield as destructibles.
Icestorm: Icy wind blows from a random direction, units that aren't sheltered behind the icicles are frozen. After several casts, the boss start targeting icicles as well (but there's always at least one icicle per unit).