Mark,
Kyoto was very nice, the only city that was not fire-bombed during the war. Lots of original temples, shrines, etc. I would recommend Nijo Castle (residence of Tokugawa Shogun), Kinkakuji Temple (Golden Pavilion), Sanjusangendo Hall, Kiyomizu Temple. There are many old shops there, but only a few sword shops (one across from the Nijo Castle if I remember right). I copied the phone book of the antique shops and had the taxi drive me from shop to shop for a few hours. I think 3 days would be enough there, you can also take a day trip via train to Nara from Kyoto. In Nara, check out the Todaiji Temple (big Buddha), Deer park, Kasuja Shrine, there are a few sword shops there also.
I also spent some time in Okinawa, you must realize everything was destroyed during the war, so any historical building is a repo, almost all buildings in Naha were gray concrete. It is very crowded, with very little nihonto. We also visited Ishigaki Island; very nice beaches, etc. it is where the Japanese go for vacation (holiday).
I have not been to Tokyo, but will next time I visit, lots of nihonto from what every one says.
I will also say the public is much more polite and eager to help than any other place in the world I have visited. Very clean also. I would check with the hotel you are staying at to see if they have English speaking employees (all the ones we stayed in did). Use them to help you make travel plans, deal with taxi drivers, etc. Also when out walking, if lost, ask students, they like to try their English, and were very helpful. You will have a great time. Mike Vinehout