料亭 (ryoutei)
A type of luxurious traditional Japanese restaurant, traditionally only accept new customers by referral and feature entertainment by geisha, typically a place where high-level business or political meetings can take place discreetly.
割烹料理屋 (kappou-ryouri-ya)
Traditional Japanese restaurants that are less formal and smaller than a ryoutei - no gardens, western style table-and-chair or counter seating, maybe just one or two private rooms at most.
旅館 (ryokan)
Although not a restaurant exactly, you can get a similar experience at high end ryokans or traditional inns: a multicourse meal served in your room.
日本料理屋 (nihon ryouri-ya) / 和食屋 (washoku-ya)
A mid to high end restaurant that serves all kinds of Japanese food. They usually have tables and chair and counter seating. A few have tatami mat rooms where you eat sitting on the floor. Most Japanese restaurants outside of Japan are of this type.
大衆食堂 (taishuu shokudou)
An inexpensive restaurant that serves many kinds of Japanese food. Most serve a mix of cuisines, or at least washoku and yohshoku (western-style Japanese cuisine, i.e. curry rice, tonkatsu, etc). There are also family restaurants or famiresu (ファミレス), family oriented restaurants similar to American diners or chains that appeal to families with kids.
居酒屋 (izakaya)
Sort of the Japanese equivalent of gastropubs. You sit at a counter or table enjoying some sake or other tipple and eat small dishes of various foods.
喫茶店 (kissaten)
A tea shop or cafe, but you can often get a tasty light meal there too, which is sometimes Japanese.
甘味処 (amamidokoro)
A shop that serves traditional desserts.
屋台 (yatai)
A traditional food cart, usually set up wherever there was a little space and some foot traffic. Foods served from yatai include ramen, yakitori, oden, soba and takoyaki, gyoza dumplings and okonomiyaki. Customers eat sitting on stools or standing up.