In snow you could have huge piles of snow and in the desert huge sandbanks.
Those seem like terrain types that you have to dig into to be hidden, and would impede movement too greatly in comparison to tall grass.
The background colours are just a little too vivid for me. I'd be tempted to see what it looks like with a more muted 16 colour version for the foreground and use the vivid 16 colours just for the sprites.
Incidentally if you were going to change the 16 colour palette, but keep to 16 colours, what would you change? 
Yeah actually I thought the same thing. Have a terrain palette and a sprite palette. Seems very sensible. Will probably be the way that I go with it.
Alternatively, if it remained at 16 colours, it's hard to go past the balance of hue and contrast variety that Arne's palette affords. The specific needs of this game are thus:
- 3 unique race colour schemes (high contrast)
- 4+ strongly identifiable team colour schemes (ideally high contrast, but perhaps not as necessary as the race colours)
- As many low-to-moderate contrast terrain colours as possible. Must be able to render ground, water, cliffs, trees and tall grass at a minimum.
The approach I took with trying to keep low value colours for the terrain and high value colours for the units was an attempt to keep myself free for being able to do things like mute the terrain colours without affecting the identity and pop of the units. It may be possible to simply mute that brown and green being used for the dirt and grass to clear up a lot of the problems.
I liked the idea of weather changing the gameplay. It would be boring if all the environments were exactly the same other than appearance. There should be some sort of balance, like maybe stealthy units leave smaller trails that fade away faster, etc, but some variety would be nice.
This is interesting, because after I made my statement about the environments needing equality, I read a book on game design, which had some pretty solid arguments for having something like game mechanics unique to each environment.
The emphasis on process intensity (meaningful choices and "verbs" available to the player) over data intensity (lots of graphics/environments/levels/sounds/story) is paramount, since the former adds to the actual interactivity of the game, whereas the latter is just kind of frills.
So considering the idea of map equality from that perspective, keeping all the mechanics the same across all terrain types essentially puts the role of maps in the data intensity zone. So to make each environment have different tactics, that would be good, as it makes the game more interactive. The question thus becomes, would the benefit of the increased interactivity outweigh the negative effects of unequal maps?
This assumes, of course, that really cool environment mechanics can be thought of for each environment type. I've already stated some of the big issues I see with the snow tracks idea (mainly the massive advantage the Machines have over the other races with it). I thought something like what was in Tiberian Sun could be cool, where you could shoot the ice an enemy was standing on to make them plummet into the water. I get a feeling this would make AoE units and abilities massively overpowered though, since they have the potential to insta-kill entire groups of enemies, and since 3/4 of Human's units have AoE, it might potentially give Humans too much of an advantage.
But I do still like the idea of say, a map with ice bridges in the middle. Wait for the enemy to cross, then destroy the bridge behind them, cutting them off from retreat, then para-drop troops into their base. Pretty cool.
Also, as I think of it, the bread-and-butter Machine units aren't hover, only the more specialised units. So it's possible there isn't TOO much of an advantage to Machines with snow/sand tracks. CrazyMLC's idea for different length tracks could work, too. The large, heavy units like Hulks and tanks could leave long trails, but light units like infantry could leave shorter ones. Thus stealth units are still less effective than on other terrain types, but they still pose advantageous use in the snow. Also this creates a choice for the player: do I take my tanks across the snow and risk being intercepted, or do I take them across the ice and risk possible losses or being stranded? Very cool.
It's possible this is just the kind of thing that has to be play tested to really see how un/balanced it is. Given that, I'll write a list of plausible environment mechanics and at some point they will be implemented and play tested. If they are good, they will stay.

This is exciting!
