Ende März / Anfang April = gut
Ende September = nein! Immer noch sehr heiß und schwül
Oktober = würde ich nicht unbedingt machen
Ende November = beste Zeit für Laubblätter für die Region, die du genannt hast
Festivals gibt es das ganze Jahr. Im Frühjahr v.a. Kirschblütenfeste. Kannst auch gerne auf
meinem Blog vorbeischauen, wo ich immer die aktuellen Festivals für den Monat aufliste.
Ich würde dir Kansai empfehlen. Von da aus kannst du ganz leicht Ausflüge zu kleineren Ortschaften machen, ich empfehle v.a. Hyogo und Shiga, aber als Basis macht wohl Osaka evtl. Kyoto Sinn. Dort gibt es auch mit die schönsten "Koyo-Spots" (Laubblätter).
Es gibt so viel zu sehen und entdecken, da würde ich mir keine Sorgen machen. Es kommt eher darauf an, was euch am meisten interessiert.