If FoW is here to stay, how about adding some different vision effects for terrain?
For examples:
-Lakes not blocking LoS
-Cliffs (wide cliffs, not roundish crater ones) add vision range for units standing on "up" (north) side. This might require randomly inverting this feature.
-Towers add vision range if you have a unit standing at the base not currently in combat.
Just a thought.