I just got back from my first trip to Tokyo, and wanted to talk about the food I had, mainly to clear up some confusion.
Bad news first: the worst food I had was in Shinjuku, at a basement restaurant. We got a set meal, that came with 5 types of yakitori, in addition to other small dishes. The first piece was good, but the second was absolutely disgusting. It was pieces of chicken separated by cartilage! Are you supposed to eat the cartilage? because it was essentially unchewable for me.
On the other hand, we had an incredible meal at a small restaurant in asakusa, near the Ginza line station. For 1500 yen each, we were served a big 7 course meal, including tempura, nigiri, lightly fried tofu blocks, miso soup, rice, and some little yellow and green stars. Not really sure what was with the stars, but they didn't really have much taste anyways.
Finally, though it wasn't Japanese, a restaurant near Tokyo station called "Ren Ren Ren" served a dish called "Ma Pow Tofu". Incredible. If you ever get the opportunity, and you like spicy chinese dishes, you have to give this a shot.