Wenn es die AVRs sein sollen, würde ich erst mal mit was kleinerem wie z.B. Mega88 anfangen. Ein wesenlicher Vorteil für den Anfang ist, dass man die im DIP Gehäuse kreigt und es entsprechend Sockel gibt und man auch ein Steckbrett nutzen kann. Für erste Versuche Reicht das auch vollkommen aus. Die größeren Chips sinn sehr ähnlich zu programmieren ein umstiegt ist entsprechend wirklich minimal (z.B. den Compiler sagen das es für einen anderen Chip ist und eventuell ein ganz paar Registernahmen anders).
Ob man jetzt eine großen Mikro, oder mehrere kleine nimmt, ist sicher etwas geschmackssache. Hier würde es sich anbieten z.B. für die Steuerung jedes Beines (=3 Motore) einen µC zu nehmen. Je nach Art der Motoransteuerung könnte da z.B. ein Mega88 reichen. Wenn man Servos als Motoren nimmt, könnte ein µC auch mehr 3 Motoren steuern.

Für die Koordination, externe Sensoren usw. dann halt noch ein µC. Da ist dann wahrscheinlich mehr die Speichergröße interessant.

Ein Modularer Aufbau hat auch den Vorteil, dass die Platinen überschaubar bleiben und man auch Teile gut Testen kann.

Für die ersten Tests würde ich ein fertiges Board vorschlagen, dann hat man erst mal nur die Software. Ob man später fertige Boards nimmt, oder was selber entwirft, hängt davon ab was man an Hardware, z.B. Motortreiber, braucht.