Thank you very much for the links!
Right now we are leaning towards Japan but Korea is very much in the running. Although the costs in Japan seem higher, the higher level of organization(at least apparent higher level) seems to me like a good thing for first-timers. Also, renting your own place and owning your work visa seem enticing.
I still have to look into it but would you happen to know if, as in Korea, private turoting is illegal in Japan? I am guessing yes but I still have to look ino it