Reisezeit: Meine liebsten Reisezeiten in Japan sind einerseits in etwa Kirschblüte (März/April bzw auch der Mai ist schön) und der Spätherbst (Nov/Dez) mit seinen schönen Farben (Momiji/Kouyou).
Also April/Mai ist gut. Allerdings!!! Ende April / Erste Maiwoche ist die Golden Week. Stärkste Innerjapanische Reisewoche überhaupt.
Merkt man preislich, und im Zug ist alles voll. Würde ich mir nicht antun wenn man es umgehen kann.
Wenn man den Trip davor rein legt hat man Anfang/Mitte April wahrscheinlich noch was von der Kirschblüte. Wobei wie Peer schrieb, im Mai evtl auch noch ganz oben in Hokkaido was zu erwischen wäre.
Mietwagen hatte ich noch nie einen in Japan. Es gibt schon Orte wo man nur schwer oder gar nicht öffentlich hin kommt. Aber gerade beim erstem Mal Japan würde ich mir das wohl nicht antun.
Andererseits ist es zu zweit vielleicht leicht günstiger. Aber in Japan gibts viele Toll roads, Parken, etc …
Wenn man aber natürlich das einfach so lieber hat wie Bahn/Bus und co dann stellt sich die Frage nicht 
Aber selbst mit Mietwagen wird man den nicht immer brauchen. Im Großraum Tokyo, und wohl auch rund um Osaka sehe ich keinen Bedarf. Im Gegenteil, den Verkehr und die Parkplatzsuche würde ich nicht wollen. Evtl für die Fahrt dazwischen. Da könnte man etwas ‚Landschaft‘ einbauen.
Eventuell Matsumoto, südlich davon ein paar Dörfer des Nakasenbon (alte Handelsstraße), über die Berge nach Takayama. Von dort über Shirakawago nach Kanazawa. Das wäre ein Teil wo ein Auto zb Sinn macht. Wenn man weiter rauf nach Tohoku will sicher auch.
Okinawa/Ishigaki sind schon auch interessant. Aber zwecks Strand/Badeurlaub würde ich da wohl nicht hin. Da würde ich auch sagen das wenn man ein paar Tage Strandurlaub mit anhängen will man eher woanders in SEA fündig wird.
Ich würde auch den 2-3 Wochen Trip auf der Hauptinsel bleiben wenn man noch nie vorher da war. 3 Wochen sind kürzer als man glaubt ;D
Radry’s Tips in Kyushu sind sicher ok. Aber doch sehr spezifisch. Wenn man Kyushu mitnimmt kann man das aber praktisch alles auch als Tagestrips von Fukuoka aus machen. JR Kyushu hat zb einen 3 oder 5 Tages Kyushu (oder auch nur Kyushu Nord oder Süd) Railpass der sich für sowas eignet.
Aber sonst wäre normal schon der ‚Klassiker‘ Tokyo + Kansai genug Programm wenn man will.
Ich würde im Gegensatz zu Radry keineswegs gleich aus Tokyo wegeilen, sondern es dort mal langsam angehen lassen, selbst wenn man am Ende dort wieder abfliegt. Zwei, drei Tage sicher. Einen Tag brauch man idR ohnehin gegen Jetlag und sich ein bisserl einleben wenn man dort noch nie war schadet auch nicht.
Es gibt in und um Tokyo ja genug zu tun und sehen.
Tagestrips nach Nikko, Hakone, Fuji, Yokohama … sind kein Problem.
Und in Kansai finde ich auch das Osaka ein guter Standort ist um von dort aus alles zu erkunden. Hab bei meinem ersten Kansai Trip auch 8 Tage ein Airbnb in Osaka gehabt und von dort aus Tagestouren gemacht. Bzw auch von Kobe aus.
Kyoto, Nara, Kobe, Wakayama sind ganz leicht zu erreichen. Sogar Hiroshima als Tagestour mit dem Shinkansen ist gut machbar. Bzw auch rauf Richtung Fukui oder Kanazawa.
Tottori, Kinosakionsen, Amanohashidate, Okayama, Ise-Shima. Alles von dort aus schon als Tagesausflug mit dem Zug gemacht.
Es gibt ja je nach Airline/Allianz sicher auch die möglichkeit eine Gabel nach Japan zu fliegen, und zb dann direkt von OSA wieder heim. Aber kann man natürlich auch umdrehen.
Bzw. wenn man doch wieder zurück nach TYO fährt kann man diesen Leg ja den Shinkansen nehmen.