What I found worked was just have one army and keep attacking places.

I usually take Dayhu Yugra, Dayhu Thissakata, Maeotis, Aghvan, Taurike Chersonesos, Bosporion Tyrranesis and Scythia as quickly as I can.

By this time you're making plenty of money.

Also, always starve them out, never try and storm their city.