Those huge Brutii n Scipii armies are pretty weak I found, I wiped out 6 full bannered armies with just 1, thats on hardest/hard also.
BTW, on the note of failing missions, when the senate get nasty, you get lots of "If you fail - The Quaestor/Censor will invesigate your faction", the key here is to have one of your guys in that position, and if not, assasinate the current one, it will make some random captain suicide instead of a family member.
Basically I don't do senate missions unless they suite me, until you reach 30+ lands under your belt, the senate are pretty harmless.
Try undermine Brutii and Scipii in the early game to make the final push for Imperator easier, feel free to assasinate and bribe them as much as you can. When you make the final push, you need to hit them hard at once, have at least 5-6 full bannered double hard armies with your top generals strategically placed throughout Italy, in ships or on land, and hit their capital cities simultaneously, try cripple them from the offset.
It's also nice to have a couple large but cheap armies ready to move in as local garrison once you captured so you can go conquer the next city.