Anyone play any of these ones?
Shintolin (Hunters and Gatherers and Builders!)
Shartak (Pirates and Indians and Cannibals and Settlers!)
Urban Dead (Barha!)
These are all somewhat similar; AP-based movements and actions, the 2-d grid style map, searching, building, fighting, crafting.
I was a really big fan of Nexus War too while that lasted. There was a really intriguing theme going on there.
The others are interesting too. Team play helps. There is also pay-for-extra-characters-or-something options but they don't help out all that much (or hurt too much if you don't).