i am playing now a barbarian scenario (noble, easy, 40 turns to start the game).
I have done pretty well I believe but I have not yet won. I have 2 more civs that seam to have much more power.
I am using my generals to create uber-units. I have 2 uber-swordsman with full-city attack, medic, march, combat bonuses, leadership and of course morality (movement 2). With this way I can move from 1 city to another and attack with very good odds (over 95%).
I use my trebuchets to bombard and then attack. Afterwards my uber units take the other 2 units in the city. My units have always at least 2 promotions when I buy them in order to select a more advanced promotion after they win their first battle and gain the first 2 XPs.
I use a lot of horse archers and chariot to deal with AIs counter-attacks (cats, spears, axemen and some stupid swords - I do not have cities man!!!).
Regarding the upgrading of units: I have not yet coped with medieval units, however the manual depicts that more advance units are made available, or not?