Cameroon -- 58 departments:
Colombia -- 32 departments and one capital district:
Guinea -- 33 prefectures and one capital zone:
Indonesia -- 33 provinces:
Kyrgyzstan -- 40 districts:
Nigeria -- 36 states and one capital territory:
Senegal and the Gambia -- Senegal, 33 departments; Gambia, 5 divisions:
Of these my favorite arrangement is probably Kyrgyzstan because of the limited border territories of each region, but I think they all have potential. What do you think?