The units i have gotten from mission are most often barbarian mercenaries
:(, perhapes it's because of lower difficult setting, i can't recall ever gettting anything decent from senate missions.

Also the difficulty seem to raise more if you keep succeeding while it drops back if you fail one or two, for example the first one i failed big time was when the senate want me to take that city west of Alexendria ... which is basically in the middle of nowhere and requires a army to be transported from Greece, I did have Alexandria at that time but it was not possible to sent a expedition from ther without losing the city instantly.... then they ask me to take memphis... again same problem.. except now that alexandria is devastated by plague making it even more impossible. Afterward the difficulty dropped quiet a bit back to blockades missions again.