Nomadic Age -- I love this idea! It should be toggable to accomidate players who don't like it. Here is how it should work, IMHO.
First of all, I will call the first era the Pre-Historic Era. You start of with your people, who are a single Nomad unit. Instead of gold your civ will have food as currency. You will start with 10 food have a -1 income each turn no mater what. If you cannot pay the food income, your civ dies:game over.
Here is how to earn food:
(1) Hunt nomadic herd units. These units will stop for a couple turns and roam certain regions. They travel in packs of several units, so you can hunt them a number of times. Every so many turns, the herds would double in size. This might lead to a Nomad civ waiting in a settlement for the herd to replenish then hunting again. Buffalo might earn 3 food per buffalo and other things other amounts.
(2) Make termporary agricultural/faishing settlements. These settlements have one population, don't grow, and only collect food from terrain. Productive terrain would allow you to gain a huge stockpile and roam for a better location/herds. When you abandon them, you get your Nomad unit back.
Fighting:
If food is scarce, you may need to eliminate the competition. In general early warfare will cost you a few turns in food, and possibly get you killed. The only real advantage, besides exclusive access to food, is the militaristic trait you will gain and the +1 HP you will gain for your first kill, +1 Attack for the second, +1 Attack for the third. All this applies to the standard Nomad(1/1/1).
Notes on Settlements:
A settlement will not generate food the same turn it is settled. This prevents players from abandoning-moving-settling in order to move every turn.
No resources of any kind are avaliable right off the bat, even bonus ones. If your settlements borders include one of them, it will be added to your "civ bonus" box. Each resource individual provides a tiny bonus to your civ later in the game. Combinations of resources provide better stuff. Combinations of many many resources will result in great advantages.
The only bonuses that are immediate are Horses and Iron. These make the Nomad better. (1/1/2)with horses, (1/2/1) with Iron, (1/2/2) with both. Because you see the change immediately after you abandon the settlement, you know where horses and iron are for the ancient era.
Pre-Historic Tech Tree:
Technology is all researched at the same rate. The tech tree is designed so that all players become Barbarians or Civilizations at the same time. Now here are the techs, in order.
Agriculture(no prequesite) (8 Turns)
Allows basic settlements and the collection of food from farming. Grain and Wheat now appear on the map.
Fishing(no prequesite) (8 Turns)
Allows basic settlements and the collection of food from fishing. Fish and Whales now appear on the map.
Burial Mounds (requires Agriculture and Fishing) (10 Turns)
Can build Burial Mound in cities.
Burial Mound - 20 Shields. Generates 1cpt.
If a settlement stays in one place for more than 5 Turns, a Burial Mound will be built. This mound remains even when the settlement is abandoned. Later in the game these sites will add 1cpt if within your borders and connected via road to a city.
Fire (requires Agriculture and Fishing) (10 Turns)
When a settlment is abandoned, a seed is planted that will form a minor tribe within 3 squares once the Dawn of Civilzation occurs.
Spiritual Thought (requires Burial Mound and Fire) (14 Turns)
Allows you to choose your Relgious tradition(I assume there will be a religion model in Civ 4).
Husbandry (requires Agriculture) (10 Turns)
Game, Cattle, and Furs now appear on the map.
Permanent Settlement (requires Husbandry and Spritual Thought) (20 Turns)
Allows you to choose to permanently settle. When you enact this option, your Nomad is replaced with a City, a Worker, a Defender(1/1/1), and an Explorer(0/0/1). The cities are limited to size 3. The worker cannot go farther than 1 square outside your borders. You can choose to settle at any time, but also choose to continue without settling. You also no longer have the food requirements and instead have gold. The food you did have now goes into your cities food storage.
Textiles (requires Permanent Settlement) (10 Turns)
Dyes, Silks appear on the map.
Stone Working (requires Permanent Settlement) (10 Turns)
Allows cities to reach population 6.
Wealth (requires Permanent Settlement) (10 Turns)
Allows citizens of cities to be taxed(1 gold per citizen).
Tradition (requiers Textiles and Stone Working) (10 Turns)
Grand Tapestry(Improvement) - 20 Shields. Generates 1 cpt.
Monument(Improvement) - 40 Shields. Generates 2 cpt.
Call to Arms (requires Tradition) (20 Turns)
Defenders(Units) - 10 Shields. (1/1/1) And completely immobile.
The end of the tech tree is a bit funny. It allows you to enter one of two paths of developement. Since everybody will finish researching at the same time, then the Dawn of Civilization occurs. When you reach the Dawn of Civilization all your Defenders turn into Warriors. If someone still hasn't settled by now, they still can wait, but will probably be at a great disadvantage. Each of the two options requires Call to Arms.
Barbarism (20 Turns)
You enter the Barbarian Era. All the seeds you generated during nomadic settlement become Barbarian camps independent of yours(normal civ3 barbs) Barbarian settlements never exceed 4 population and cannot build settlers. Instead when population grows beyond 4, a new Barbarian Settler(1/1/1) appears. They get to keep the Pre-Historic Improvements and still build them. The tech tree for the Barbarian Era is mostly units and resource improvements and special abilities, but lacks culture increasing improvements.
Civilization (20 Turns)
You enter the Ancient Era. You are a normal civ and proceed through the game as such. You can no longer build the Pre-Historic improvements. The seeds you generated during nomadic settlement become Minor Villages.
I won't go into the Barbarian Era techs, but will mention a special point. At the end of the Barbarian Era you can choose between two paths again.
Call of Civilization
This option allows you to enter the ancient era with w/e techs you have researched/traded for. If you have all ancient era techs, you will start in middle ages as a civilized faction.
Warrior Kingdom
This option leads you on to the Warrior Age. You will have specialized buildings and even greater ability for carnage, but your cultural achievements will not be impressive. You will continue as a Barbarian.
During the Warrior Age you can decide at any point to research Call of Civilization, but you will then start with whatever techs and what level you are when you finish researching CoC. This means you can still be a barbarian well into the modern age. The barbarian techs support units all the way to Terrorists.