Yeah, a big cap may help. It all depends on for HOW LONG the start up "problem" happens.
If the cap isn't big enough, then it won't work.
And as pointed out by Robin2: Make sure the power supply to the Arduino is isolated from the supply for the motors.
Either a whole different one, or a lot of good decoupling.