Nothing is as boring as an empty 256*256 map. IMO it's better to create a good terrain (perhaps even go for something smaller than 256*256) that is original, good looking, and re-use your terrain for multiple quests. Don't make 10 places on the map with trees, just stick to 1 or 2 forests.