Bos Wars
Bos Wars is great fun. It's very quick to pick up, but there's lots to learn to master the game.
The key areas for improvement are:
A slower slow game speed
A faster fast game speed
Random map generator
Navy
Differentiated sides
Ability to set harvesters to energy only/magma only
Screen resolution/size
Tech levels
More unit stats: speed, rate of fire, etc
Transparency on difficulty levels
Ability to build and destroy bridges
I would suggest that the random map generator is probably the priority for maximising replayability. I think a random map generator works best when the player has a lot of control.
map size
% of map for each terrain type (including bridges)
number of players
starting resources per player
starting units per player
tech level per player (i.e. ability to restrict the build options per player)
number of magma sites (of each intensity)
amount of map known (%)
fog of war on/off
magma sites near starting positions or spread out
bottlenecking (minimum width of the land route between the players starting positions) (zero where only a sea route)
starting positions (corners/sides/centre/random)
victory conditions
Types of random maps:
Mirror map
Level where can only get to enemy by harvesting energy/magma