I would vote for Taiwan or Okinawa in May, leaving other big cities in Japan for the future.
To enjoy Okinawa the most as a family, driving is better than taking buses but in Japan they drive on the left side of the road.
Okinawa has good reputation as a family vacation destination. I've been to the stalactite cave Gyokusendou, it's gorgserous.
In my opinion, traveling to other parts in Japan with kids is better when they're old enough to remember the trip.
You would have more options with bigger kids and the cost of the whole trip would be much more worth it.

Life style in Taiwan is pretty relaxed.
I would not recommend driving in Taiwan. Taipei has convenient public transportation and lots of taxi.
One kids-friendly resort on the top of my head is Silks Place Yilan Hotel, located in Yilan, Taiwan.
It's popular among Taiwanese parents, some would stay inside the resort for their entire stay.
Parents would watch movies in the movie theater while the kids enjoy outdoor inflatable playground or the childerns' museum.
The resort has a play area designed for kids 0-3 years old inside the children's museum and a big pool.
Yilan city itself is a tourist city close to pacific ocean.