I'm somewhat of an old CivIII vet. Was playing and winning on random Emporer starts before CivIV came out (eagerly anticipating Revolution). I no longer have a comp that plays CivIV, but I can still play III so I'm back to the game that got me started with Civ for the time being. Keep in mind I skimmed through most of these posts, and without a screenshot or save it may be difficult to give really accurate advice. But I'll give it a go.
#1 DO NOT EVER PLAY CHEIFTAIN!!! You learn many bad habits on this level, and they are all hard to break. I started here, and it hampered my development for a long time, because I always wanted that wonder, I was used to always having a tech lead, and I never had to speed my expansion, because I always outpaced the AI. I see you haven't been playing much with Cheiftain so this is good.
#2 Forest chopping and pop-rushing. You seem to be focused on playing the higher difficulties and pop-rushing and chopping are, IMO, essential above Monarch. Need to complete that building a turn or two faster? Chop that forest. Need to crank out a library in a town that has no really productive tiles....pop-rush baby, pop will grow back, and they can't stay mad forever

Be careful though with pop-rushing, unhappiness can and will bite you in the ass if it goes unchecked.
#3 NO WORKER AUTOMATION!!!!! EVER!!!! These little units are arguably the MVPs of every game. The way to make up for the advantage the AI has above Regent is smartly used workers. You can maximize your city efficiency with these babies, ultimately making you more productive then the enemy AI. If you can outproduce him, even with the horrible RNG you can beat him. I've had games where I've fought with Swords and Trebs against rifles and won. It's hard and takes much more time, but use your workers smartly, outproduce the AI, and you can't lose.
#4 BUILD MORE WORKERS!!!! Far too often new players do not have enough workers. Don't build so many it drains your economy, but you need to have enough workers to transform your terrain quickly, and new lands you conquer from the AI as well.
#5 Slaves are good. What's better then a worker? A worker with no upkeep. Although they work slower, capture enough of them and you can replace your worker force with your enemies. (Wont happen often, even on Emporer AI workers are fairly hard to come by before the middle ages) Most games these bad-boys will be an excellent addition to your workforce, and by the end-game they are perfect for cleaning up pollution....again if you have enough, disband your workers and go to a completely slave driven workforce. Saves money....this leads me to my next point.
#6 Money = whatever you want.....so long as you can cash rush. If you can use cash t rush, money will build those improvements in newly conquered towns, research that tech to give you the edge, pump out those troops so you can destroy an enemy capital before it launches the spaceship. This is more a late-game tip, but don't be afraid to spend that money if you can.
I think most everything else has been covered. Don't build Ancient wonders above Regent as a rule of thumb. Regent you can usually nab one or two. Take them instead. 300 sheild for a wonder = 10 Swordsmen to take that wonder plus the profit of having a new city. To be honest, I don't ever build wonders before Industrial Age. Even then I usually only build Theory of Evolution and Hoover Dam, by the Modern Age the game is usually won, so tend to snatch up all the wonders to make up for the lack of early ones
The only exception to the wonder rule is if you're using the Great Library gambit. Though it is a crutch, and I don't recommend it while you're learning. It's more a necessity if you're on Deity and above. Demigod maybe, but I've dabbled in Demigod with some succes and I didn't find the gambit necessary.
Otherwise, like I said it's probably been covered already, close city spacing is much more superior to spaced out (though I've been guilty of keeping my cities next to my capital to spaced out myself) You can always demolish that city later if you need or want to. Again, it comes to the point of outproducing the AI....more cities = more sheilds earlier in the game when they count the most.
One last tip now that I think of it. Moonsinger was/is a god a CivIII. I learned alot of what I know from reading through some of his exploits. Moonsinger played a game on a modified Diety (before there was Sid) with basically the same settings as Sid. I'm too lazy to find it but it would benefit you greatly to read through it. It's very interesting to say the least. If I can find the post I'll update it here for you.....some old vets around may know the one I speak of and beat me to it.
Welcome and best of luck.