Sharky,
The level that is even is Regent. Monarch (where I'm at now) gives the AI some production/research advantages. Emperor & Deity are where it gets silly.
REX = Rapid Early Expansion. Basically, pump out settlers for all you're worth. There was a thread all about this a while ago. As for the first worker, it depends on the starting terrain, but...
Keep in mind improving various terrain will do (or NOT DO) under despotism. For instance, if you have a cow on plains (2 food, 2 shields), irrigating or mining won't do anything until you use a better form of government. Therefore, the most you want to do there is build a road. Irrigating wheat on floodplains does give a bonus, and that is a good idea to help early city growth. I always mine (step 1) and road (step 2) grassland. I often reverse this order if I'm playing an industrial civ.
Expansionist, unless you're on a large/huge map with lots of land, kinda sucks. Sure, you can get lucky with huts and you do have pottery to start, but it's a civ trait that does not give benifits throughout the game. All of the other traits do.
Start position is crucial. Restart until you have a good one. By this I mean fresh water (no need for aqueduct) and a couple of bonus tiles, like wheat or cows.
The AI expands like crazy (as you've noticed), so you have to keep up - at least in the beginning. After you've got a good core built up, and access to a couple of luxuries, let the AI continue to waste resources plunking down cities halfway around the world on tundra (though understand you may have to take them by force later).
I, too, am a Civ II vet. The first time I played Civ III, it was chieftain... then warlord... the regent - where I got beat up for a bit... and now Monarch, which still can give me trouble (the first few games kicked my butt).
Sorry for the length of the post... it's a complicated game, ya know?
-Arrian
EDIT - Vel beat me to the punch, LOL! Warrior, Warrior, Settler is what I do, too, the only difference is that I will mine a bit to boost production of those warriors early on... and so it's prepared to start on a wonder when I'm ready to hand off settler production to other cities. "Worker farms" handle producing my road-builders.