I ate at the low-priced restaurant at Taillevant-Whatever and was disappointed.

If you are not aware that there is an English translation of the Zagat Tokyo guide, referenced above, you now know -- get it. The Japanese raters do have some unusual ideas of what constitutes good Western food, but the book is still the best available.

Kozue is reputed to have the best food at the Park Hyatt Tokyo but the most famous restaurant there is the New York Grill, which is an (!) American-themed restaurant. Since you are not staying at the Park Hyatt, email now if you want a booking. The food is definitely not the best in Tokyo, but the experience in total is memorable and it actually is a bit cheaper than Kozue.

My favorite hole in the wall French restaurant is Canard, with all of 6 tables, in East Shinjuku. You will never find this place without a map, ask the hotel. Booking essential.

There is a good small tempura chain called "Tenichi" that has a branch close to your hotel. Sit at the counter and watch the chefs.

A non-obvious thing to be aware of is that most of the high rise office buildings near your hotel have restaurant floors at or near the top, often full of reasonably priced choices (you won't want gourmet EVERY night). One of the buildings even has a drag queen night club in it!