how to design power for arduino and servo
Since Arduinos have modest current consumption, any linear regulator will do. I own a few Atmel boards which have a 662K regulator on them, these can handle 6V just fine.

I'm not sure whether adding a large cap to protect from voltage drops will do any good. By the time your battery drops from 6V to 3V under load it's probably unsuitable to run the servo anyway. If you need your Arduino running while the servo is struggling to start, I'd add a small ultracap (0.22 - 0.5F) to Adruino power lines. You'll need to carefully evaluate the power consumption to know how much time exactly you can run off this backup power.

If you want to maximize battery life, I suggest you look into low power modes provided by Atmel controllers. Take a look at this library for example.

Using a switching regulator will probably worsen battery life: these regulators are only efficient when substantial power is needed. At currents below 1mA linear regulators beat switching regulators by orders of magnitude in terms of efficiency - the 662K I have mentioned consumes only 1μA, while an LM2575 wastes 5mA.