If you want it as small as possible, you might have to build a custom PCB; there are a few options. One thing you could do is look at these:http://www.pololu.com/catalog/category/12
For the "pre-built" option - a standard Arduino and the Pololu Mini Maestro 12-Channel (http://www.pololu.com/catalog/product/1352
) would be a good dev platform; from there, you could build your custom PCB using an ATMega328 (plus caps and crystal, etc - with Arduino bootloader), plus one of Pololu's servo chip controllers (http://www.pololu.com/catalog/product/280
). That would make a fairly compact device.
Or - you could keep it "all Arduino" - and use two ATMega328s connected via I2C (using the wire interface library - http://www.arduino.cc/en/Reference/Wire);
one would be the "master" with all of your controlling code, the other would be the "slave", driving the servos (using the servo library - http://www.arduino.cc/en/Reference/Servo
) - the Servo library can control 12 servos directly using the 168/328 (IIRC). What you would do is essentially create the equivalent of the Pololu controller on the ATMega, able to take commands from the controller ATMega (the master).
While in theory you could potentially do everything in a single Arduino/ATMega328 controller, running all of your code and the Servo library, etc (and it would certainly be worth pursuing!), spliting the tasks up will free up memory and processing power, so that the controller could act and do other tasks at the same time without any potential for "twitching" or other possible issues (or slowdown of your main code). It may or may not be a big deal, though, so the single controller approach is worth trying out first.
BTW - I've given thought to the idea of a quadruped in the past (I know I've posted about this before); in theory, one should be able (possibly) to build such a device for around $100.00 USD, if the PCB was custom, and you had the parts designed to be made from PCB material or laser-cut from acrylic, plus used some of the small servos on the market...