To put this shortly.
If you manage to be aggressive in the start game you can win any victory condition on any level.
Personally I played around 30 games on chieftain learning the game mechanics and also read a lot of helpful advice on these forums. I skipped Warlord and went straight for King and two things i noticed early.
1) I had to be quicker on early conquest or the AI would already have Archer armies.
2) Go to war even if you can't take their cities. The reason for this is simply put that the more time the AI uses on "obsolete" units instead of research, the better your chances to win.
3) The 100% on chieftain and 50% on Warlord to combat makes a HUGE difference, so you will usually have to get your units promoted or attack with a class with basic attack rating higher then the defender, and this is were the tech comes in.
My games are usually played out like this (even on Deity)
a) Either full science for HBR (no food, no hammers) and build horsemen ASAP for faster movement and added attack strength, or build warrior army ASAP. Attack 3 times barbarian villages (4 usually since it takes 2 attacks to get the bonus from taking a village) to get promted to veteran, and hopefully by this time you have found the first AI.
b) If you can attack from a Hill do so, and once your army is in place attack. If he has an archer army, withdraw and leave him for later picking up troops going outside his city, and any settlers etc. Scout around for your next prey as well, he might not be as fortunate to have archer army

c) You have now gotten your first AI capital, and time to switch to growth/science or continue with units to get a second AI capital and maybe an additional city depending on how long it took.
d) By this time you have secured your area, so beeline for code of laws unless you have been so fortunate to get the pyramids from a relic. Switch to republic and start settling your land, i advice to use sea regions as science and gold are your friend. I usually do a 2/3 science and 1/3 gold. I don't care much for production as i rush buy what i need.
e) You now have the game in the palm of your hand, and can focus on cultural, science, economic on conquest after your desire.