It is not a good idea to have the Arduino and motors share the same power supply, for the reasons you posted, as excellent power supply decoupling is absolutely required.
The safest and simplest approach is to use separate regulators, one for the servos and another for the MCU and peripherals.
Make SURE that the servo regulator can handle more than twice the servo stall current.