Yeah this seems to be one of the main problems with the game with the larger mediteranian cities. It is the opposite with the northern barbarian towns, most seem to start with less than 1000, and the need to have troops coupled with the need to have taxes high in order to get a little bit of money, it makes getting anything going really tricky. I have been tempted before to take my entire starting army with a barb faction, put them all on a boat, except the family members who I devide among my family. Then I would take them all the way down to the mediteranian and take a tour, capturing and enslaving carthage, then doing the same for Rome, before heading down to Alexandria and trying to take it with the troops I have left.