Okay, so this is a flying tour. A few suggestions:
1. If you are a food tourist even slightly, you will almost certainly be visiting Tsukiji fish market in Tokyo. After the auctions and such finish, you can stop by Aritsugu Tokyo or Masamoto Tsukiji, whose shops are in the market. There are a few others, but these are the most famous. Aritsugu Tokyo has excellent prices and service, and highly respected knives.
2. In Kyoto, you will probably visit Nishiki Market, in which you will find Aritsugu Kyoto (no connection with the Tokyo branch since the mid 1920s, incidentally). Their service is wonderful, their knives are very good, and their prices are very high.
3. The only other place I know much about knife shopping is in Osaka, and I think is rather a waste of time, in the sense that it's not someplace you'd otherwise consider visiting, and it's kind of dirty and blah. Kappabashi in Tokyo is somewhat similar: you're not likely to visit for other reasons, so skip it.
4. I would very, very strongly recommend against buying an usuba. It is perhaps the most irritating knife design you'd ever use, and it does not cut or handle the same way as any other knife. I do not think it is worth the investment of money and time that it would take, unless (a) you are a vegetarian or very close to it, and (b) you want this knife to be a major hobby unto itself. I would instead recommend purchasing a 240mm or 270mm gyuto, which is basically a Japanese-made chef's knife. If you want something cool, buy a wa-gyuto, which means a gyuto with a Japanese-style handle, which looks great and makes very little difference -- certainly nothing negative -- when actually using the thing.
Aritsugu Tokyo makes these wa-gyuto's primarily in their A-style, which means a semi-stainless steel that is notoriously tough; while hard-core enthusiasts generally think the knife is a little thick, I doubt very much that you will find much to object to here. The prices on the A-style knives are all very good, and those things withstand frightening abuse, so you don't have to baby it. Of all the many and varied options available to you at this point, that would be at the top of my list.
The obvious alternative to a gyuto is a yanagiba, i.e. a slicing knife, but that will be considerably more expensive and less useful.
Aritsugu Tokyo, A-style wa-gyuto, 270mm -- list price Y14,000
Aritsugu Tokyo, bottom of the line baseline yanagiba, 300mm -- list price Y18,000 (they do make a cheaper A-style yanagiba, but the experts all seem to agree that this is not a good idea -- I can't really comment, personally)
If these prices seem very high, get used to it. I assure you, those are terrific prices; most places will be a good bit more.
Remember to keep your receipts so you get the taxes back!