Stepper motor causing Arduino brownout?
There is a great deal of variability when looking at high speed changes in power draw.  It isn't as easy as thinking about what might happen at DC.  Some of the issues can be based on the length and size of conducting wires, as well as the configuration of power routing.  This applies in both wiring and PCB routing of a power system.

It is possible common to have a power demand pulse quick enough that you have to think of power bus as a transmission line, rather than a lumped circuit element.  The inductance of your power supply wire will resist current flow enough to drop the voltage a significant amount at the end of the transmission line.  So in this situation, a diode and capacitor may solve the problem by keeping Arduino voltage high until the current can make it down the wire to fill the need.

It is a good idea to isolate the control and high power demand variation circuits.  This doesn't have to be as much as a separate power supply, but could mean just not sharing long runs of power supply wiring, before T'ing off to each other.