that's a concept i've always liked, and never seen made.
the closest i've seen to it is the original AOE's early stages, when you were still slightly hunter gatherer; but still, that's not it yet.
for years i've had these ideas for a strategy game set in the times of early man,
before being settled,
like you guy's mentioned, instead of empires/civilizations, it'd be the different hominid species, cromagnum, neanderthal, aflorensis, etc.
and intead of cities, you'd have packs or tribes.
and then there's the whole thing about discovering agriculture, developing warfare, inventing tools.
i'm sure it'd make for a great game!
sorry, i just had to share!