Standard PCB trace widths

If you have traces forking off the main trace, or separate traces running directly to the regulator then these only need to be wide enough to handle the 500mA for the Arduino.

You can think of the power distribution a bit like a river with tributaries. The main "river" needs to handle the total power for everything and the tributaries need to handle the power for whatever they lead to. Remember to think about the full loop (e.g power and ground traces) for everything.
If the Arduino was directly in line to the servos (i.e. the servos were downstream of the Arduino, so it goes Regulator->Arduino->Servos) then the traces would need to be rated to handle the Servo current too.

Usually it is best to keep the high current stuff on a separate trace, or nearer to the supply, as the more of the route they share with sensitive components the more they can interfere. With planes a similar logic applies, though positioning is more important as you have to assume the path of least impedance will be taken (not always the shortest path)
Edit - As Kortuk mentions a plane is preferable if possible. A dedicated solid layer (i.e. no routing, or if some is necessary try and make it in the same direction to current flow so it does not have to "take the long way round") is best but a fill is certainly useful also.

A reputable PCB house will solidly deliver their minimum standard track & spacing.

Some will let you try finer at your risk and some will reject your work outright if under spec.

I assume that you are using a temperature controlled iron. If not, do.

If you are not confident in your own soldering abilities and you have plenty of room then fattening up tracks and especially pads associated with through hole parts does no harm. I'd give the through hole headers as much copper as you reasonably can - especially if the board is NOT PTH (plated through hole). With PTH you get substantially more strength. If the board is single sided (probably not, but ...) then you want to take great care with through hole pad soldering and due care with everything else.

SMD part pads should be suited to the part and you have to learn to accommodate them rather than them accommodating you.

PS: Others feel free to contradict or improve anything I've said. I have very substantial soldering experience but there is always good stuff and ideas to learn. ________________________________

Related: This excellent reference -
TI Analog Engineer’s Pocket Reference - 4th edition
as well as a vast amount of other useful material
it provides some useful information on PCB track current/ voltage drop / heat / fusing issues. Especially pages 55-68.