I am guessing that you are looking something different from Tokyo, Osaka, and Kyoto? I agree that Okinawa will be good choice, tropical island feel which is different from Tokyo, Osaka, and Kyoto. There are places you can visit in Okinawa to experience local Ryukyu people’s culture and history which is very different from what you saw at Kyoto.
Along the similar reason heading north to Hokkaido will be different from Tokyo, Osaka, and Kyoto. Vast open space where you may not think place like this exists in a small island nation of Japan. Experience local Ainu people’s culture and history which is very different from old city Kyoto.
Another place different I can think of is Nagasaki. Nagasaki is where Christianity has flourished once, and when Japan closed the door to outside for three hundred years Nagasaki port remained opened to Dutch. Also, historically Nagasaki had trade with China. I do think Nagasaki has different feeling from Tokyo, Osaka, or Kyoto because of that.