Bottle Nebula was an easy choice for me: Distinctive before and after (plus stages of after), enough story to explain the changes, well-executed, and a perfect reason to have a before and after map internal to the map itself.

Blackwater wasn't finished. Changes in Terra Incognita lacked any story (map-internally anyway, which is all I count when judging). Cataclysmo seemed like it was just the same map twice with a change of color. Lost City of Ubar was pretty good, and would be my runner-up, but lacks the neat internal logic of Bottle Nebula (why make a map of hole in the ground?) and was just overall less cool than engineering a nebula.