Simple pathfinding from object to object is relatively easy to program, the object to move to would be randomly chosen based on the importance of the building.
Only merchants, the trainer in the barracks and siege engineer would require a new animation. Walking animation and basic battle animation will do for the rest. Just make sure the catapult hit around their target, which is only AI coding.
Make cities look different from eachother by placing buildings at different places, and more or less on certain places (based on terrain, near important objects, etc) than other cities should not conflict with any pathfinding. The AI will only have to know where the buildings are in the city, which isn't too hard to make and would, again, be a major improvement to the game in my oppinion.
Oh I absolutely must agree, AI goes first. But while they're at the AI they could aswell take a look at the AI in the city..? Not?
Double click on a city to view the city menu, click on 'show settlement details', a new menu will appear on the left (a very important one too), last step, click on 'view settlement on battlemap'. Enjoy.

Image to help:
http://img90.imageshack.us/img90/3436/cityviewlx7.png