I'm also in favour of multiple battery packs for this kind of large system.
This way you'd be expecting a fairly managable 6-9A continuous per battery pack, they'd have to be able to handle up to 20A peak, so 2.5mm² wires from battery to servo controller should be enough. Pick batteries that can handle 20A comfortably, and add a 25A fuse to protect everything (a short will result in a fire, fast with that kind of battery - either from the wiring or the battery itself).
A separate 3xAA pack for the Arduino is a good idea, likely helps keeping things stable.
2s LiFePO4 is another good candidate for battery, and those are easy to find in higher capacity as well. About 7V fully charged, so nicely within spec of the servos. Also no issues with the battery itself bursting into flames, like LiPo likes to do when abused too much.
LiPo OTOH is easy to find in high C ratings. I've seen ratings as ridiculously high as 100C and even more...
It's an SBEC where you can select 6V output with dual output leads(!), which will be perfect since I will use two servodrivers. It states that the batteries can be "2-12 cells li-XX [...]", and I assume my 4 ordered 18650 batteries can be used with this if they are in 2S2P? I'm very new to all these types of batteries, but if I've understood it correctly: they are lithium-ion which would be an acceptable source for this SBEC (and therefore the servos)?
I also found another similar SBEC from a store located in my country, and it's still 20A, 5-9 V out and the input voltage is 6-50.4V. This is all fine, but they wrote "(atleast 3S lipo is recommended)". What would happen if I use 2S2P 18650, since it isn't recommended, but still is within the voltage input range? Lower efficiency? Catastrophic failure?
2S LiFePO4 also sounds wonderful, but it would be good if I can use the 4 18650 3.7V batteries (also holder and charger) to power the servos so that I don't have to order more batteries (and their accessories). This is already my most expensive project to date
2S2P 18650s may well be o.k. depending exactly what they are. 18650 just defines the physical size and there are all sorts Li-ion 18650 batteries of variable quality. In general the higher the quoted capacity (mAh) the lower the maximum current they can support. Do you have a link to the ones you've bought?
Oh, that explains a lot. Sorry! They are 18650 flat top Li-ion sony 3.7 V 2600 mAh with a max current of 30 A. Here's the link . It's a Swedish site but you can change it to EN.
They look good provided you make good solid connections to them. The Hobbyking SBEC should be o.k. Don't know about the other one but with a well designed switching regulator any specified input voltage should work. I guess they might be worried about the 30A input current needed to boost a 6V input up to 9V 20A out. Not a problem for you.
The wires on that image look very thin for 20A continuous operation. Even if you nicely balance it on the output, and each of those wires has "only" 10A to deal with. I'm expecting at least 1 mm2 for 10A.
Even at an very good 96% efficiency of that converter (not specified in the product page so could be more like 90-95% - as a rule of thumb the greater the voltage step the lower the efficiency) that's 20A * 5V * 4% = 4W of dissipation, in the form of heat. Now the device does appear to have a pretty decent heat sink, but you'll have to remove the heat shrink to actually make it do its job.
