One method that I think looks better than the paper-thin method is the SimCity 4000 method:

Using this will ruin the look of maps like Tropical, though.
TBH I was just planning on making every new map surrounded by lava / acid / cloud / fog / space for maximum pretty. Behe's "Moor" does it really well: http://springrts.com/phpbb/viewtopic.php?f=13&t=23411