And to be a bit more specific - if you're interested in good eating, it's not a bad idea to do a little advance research rather than just asking random people you meet once you get here. Of course it's also fun to just wander around and find someplace that looks good, if you have the time, the weather is good, and it's not a Friday night.

If you find a specific place you want to go, a reservation is always a good idea. Places that don't take reservations are pretty rare. (Obviously places in Tsukiji Market where people wait on line for three hours don't take reservations, but that's maybe not the best use of your time when you're on vacation.)

There are lots of great tonkatsu places in Tokyo. I especially like Butagumi in Nishi-Azabu and Horaitei in Shibuya; among the chains Katsukura is quite good, and since they're based in Kyoto they also have branches there and in Osaka.

I've never heard of sushi restaurants running out of fish at 7pm; of course it's possible that there's someplace like that somewhere in Japan, but it's certainly not common.

And as Mr. Pickles says, Chowhound usually has good restaurant advice for Japan.

Just to be clear, I said "start to run out" at about 7-8. I'm not saying that my experience is the standard, but I've had several occasions where certain types of fish are no longer available at around that time.