I will add to downhand's answer, which I mostly endorse (especially the part about the ferry!) I will give some alternative suggestions about some of my favorite places off the beaten track, especially if you like walking.
I would personally spend somewhat less time in Tokyo and Seoul -- they are delightful places both, but in my opinion the tourist sights in both places can be missed. The fun part of these cities, in my view at least, is just walking around and seeing everyday urban life.
I'd probably skip Kobe, unless your itinerary is otherwise short on urban Japan. It is a delightful city (indeed, I am there now for work and having a great time!) but there are pretty much no tourist destinations.
In the outskirts of Nara, I would very strongly recommend walking all or part of the Yamanobe Road. I did all 31 km of it this past Saturday, and it's easy to do just half of that if you prefer (there are lots of train stations near the route). It walks through rural Japan, at the side of mountains, through small villages, past Buddhist temples and Shinto shrines, and past the ancient burial mounds of emperors from ages past. If you've ever seen My Neighbor Totoro, or any other animation by Hayao Miyazaki, imagine that it came to life and you got to spend all day walking through the set.
In Kyoto, there are lots of places off the beaten path. You should definitely do Shijo-Kawaramachi, Yasaka Jinja, Kiyomizu-dera, etc. like most other tourists, but my favorite place is Fushimi Inari Taisha. It is open at night, which is a wonderful time to go. A bit scary, in a good and exciting way! Also check out Arashiyama, especially if you don't otherwise see much of small town and rural-ish Japan. Nanzen-ji is another beautiful temple -- it supposedly closes at 5:00, but when I was there they only closed some hall with some Buddha statue or something and you were free to walk the breathtaking grounds in solitude.
If you like baseball, check out a game anywhere in either Japan or Korea. The most raucous sports crowds you'll see outside of South American football.
On your way west to Fukuoka, a convenient stop is Himeji -- which has the most beautiful castle in Japan (not a reconstruction like many others).
Once you're in Korea, you might visit Haeinsa Temple -- a beautiful; stay there overnight and visit first thing in the morning, before the crowds show up! In Gyeongju, rent a bicycle -- a fantastic way to see the outskirts of the city and the surpassingly beautiful countryside.
If you enjoy hiking, I recommend a trip to the summit of Mt. Seorak. It's a doozy, so if you want to day-hike it get started early (e.g. 6:00 am). I recommend starting from the north side and descending the south: at the south end of the climbing trail there is an oncheon -- hot springs -- complex and you can take a hot bath in a huge bathtub for two hours. After a long hike you will definitely appreciate this (not to mention a heaping plate of galbi). If you skip the mountain hike I recommend a trip to another hot spring bath at least once -- they are called oncheon in Korea and onsen in Japan.
You are in for a treat. Have fun!