A cool place that's fun to take people is Seiryuumon. Seiryuumon is a small chain. The one I went to is in Shinjuku from the East exit a few stores down from the old Kinokuniya bookstore (vs the new Kinokuniya near the south exit) It's a chinese restaurant that is very very themed (ie, decorated). It's a great place to take somebody when you don't have any special idea of where to take somebody. The one in Shinjuku is two stories and each floor is completely different though they both have the same menu. Some tips: One, the name of the restaurant is written in Kanji so you should ask somebody for directions unless you can read Kanji. Two, order alot as the dishes are small (it's almost like eating dimsum) 4 to 6 dishes for each 2 people. Three, unless you are a party of 8 to 12 you'll probably share a table with other people. Just FYI.
Each one is themed differently but they all have the same menu.
One interesting story: I went to the one in VenusFort in Odiaba. The entrance is themed like a Chinese prison. Some of the Seiryuumons have an *event* that happens about once a hour. At the one in Odaiba part of the eating area is raised like a stage. During the event curtains close separating the stage like area from the rest of the dining area and steam blows. Some guys that happened to be sitting at the table on the stage area, when the curtains opened they started doing standing flips. I asked the waitress and as I thought, they were not part of the show. It just happened that a gymnastics team was sitting up there and decided to show off. Pretty cool.