Early on, I tend to prioritise the construction of the most profitable buildings for each settlement. Ports are first priority, then possibly paved roads and traders. Also, don't feel you have to build every type of barracks and stables in every settlement. Have one settlement focus on cavalry, another on infantry, and one on missiles. That way you save yourself several thousands of denarii to waste on throwing expensive parties, or rather on your armies. Finally, for your most secure settlements (ones where the enemy can't get to without going through others first), don't waste money on garrisoning expensive troops. Peasants and militia will do. Once you have a secure financial base, move on to the next city and take it by force. The extra income will be welcome. Don't worry if you see negative incomes on the strategy map for your cities, they're all still adding income.

Also...

At the very beginning of the campaign, you can sometimes get a 1000 denarii or so from your neighbouring factions by asking for money in return for a trade treaty. After the first turn or two, that no longer works though and they have the cheek to ask you for money instead. Another way to get money from the AI (aside from the selling of maps), is to ask for money whenever they ask something of you. For example, if they force you into becoming their protectorate - always ask for money before agreeing. You should be able to wrestle 5,000 or more out of them, but aim higher and really drain their coffers.