Whenever I go out in nature, I always get the urge to make an outdoor encounter. Real terrain is very interesting and complex. One issue with interesting outdoor terrain is that the map will probably take a long time to draw, so you don't want to do it mid-session.
I want to play a battle that starts out in a heavily forested area and ends in a desolate wasteland

.
Here's some stuff you could include:
Small trees - place on edges or corners of a square. Characters can't pass through them, and they may provide cover. Trees which take at least 20 damage are destroyed. Trees which take fire damage catch fire, and afterward deal 1d6 damage to creatures which start their turn next to it.
Large trees - fill squares and provide cover; characters can step diaganolly through corners. Trees which take at least 50 damage are destroyed: their stump becomes difficult terrain, their trunks fall in a random direction, creating difficult terrain where the trunk and branches land. Trees which take at least 5 fire damage catch fire, and deal 2d6 fire damage to creatures starting their turn next to them. Trees can be climbed (DC 15); a character in a tree can't be attacked by melee attacks, unless the attacker is larger than medium or wielding a reach weapon; characters in a tree have concealment, as do enemies they attack; characters in the tree when it falls take falling damage for falling 20 feet.
Bush - Difficult terrain. Bushes provide concealment. Bushes which take 20 damage are destroyed.
Ravine - Characters in a ravine have cover against enemies not adjacent to the ravine (a ravine which turns should be treated as two separate ravines for this. Exiting a ravine costs an additional square of movement.
Stream - Difficult terrain. Characters who start their turn in the river must make a balance check (DC based on river speed, DM should choose) or fall prone.
I think you want the terrain to be pretty full of stuff, or else if will be too easy to just ignore the terrain. You also want to have terrain they can interact with/destroy. You could also have animals which are neutral unless injured.