That looks really good! The lower left stone rocks, giving the map a certain depth. Adding the palace there would create a bridge to the viewer or reader in this case. I don't know if a legend in the map will fit. Perhaps it will be too much and draw the attention away from the city. A few gardens next to some houses is a good idea, perhaps just adding some flowers is enough?