Introduction
Going out to eat isn't too expensive, and it is a good way to familiarise yourself with traditional Japanese dishes. At lunch a lot of places have teishoku (定食). This is a set meal, often changing on a daily basis, which includes rice, soup and a salad. It sometimes means that you can try the more expensive a-la-carte dishes at a fraction of the cost.
Quite often people go to restaurants and pick things at random, which can work out well. However, the menu might also be viewed as a kind of minefield - some might not like to put their fate into the Kanji God's lap.
Restaurants may have English or picture menus, and many have plastic models of the food outside. If you want to try your hand at ordering, then I have included links to generic menus. These should be applicable to most places.
A lot of the food below may well contain traces of fish, usually used in the stock. If you can't have any meat or fish, it can be quite difficult to eat out. It might be advisable to become a regular somewhere, get to know the owner and then ask them to make dishes without meat or seafood. A few places to eat can be found on the following map.
Somewhere between a Japanese pizza and an omelette, this is made from a basic mixture of flour, egg and water. A variety of items are added to this - the name literally means 'as you like it'. Ingredients range from meat and seafood to cheese. Pancakes are topped with mayonnaise, brown sauce and dried fish flakes. It's cheap, filling and best of all, it gets cooked in front of you. Given that you are able to watch the cooking process, it should be possible to leave things out if you are vegetarian, or fussy. When ordering, just ask for _______ nashi. 
Soba is a traditional Japanese noodle, a little thicker than spaghetti, made from buckwheat and wheat flour. Udon is also made from wheat flour and is slightly thicker. There is a cold version, usually accompanied by a an assortment of compliments, or a hot version served in a hot broth.
The cold variety is first dipped in a sauce before being eaten, while hot soba or udon is eaten straight from the bowl. 
Although this is one of the most famous Japanese foods, it isn't ideal if you are a vegetarian. However you can get egg, natto and umeboshi, a salted pickled plum, on sushi. If you have eaten it outside of Japan and didn't like it, it is well worth trying again. The fish is a lot fresher and as a result, it really does taste better.
Kaitenzushi, conveyer belt sushi, is a good option. The quality's not bad, it's fairly inexpensive and there is no need to order - you just see something and pick it off. The plates are often colour-coded according to how expensive the dish is. If you don't see something you want, you can ask the waiting staff for it. Soup can also be ordered a la carte.
A word of warning - it's probably best not to go for that piece of fish that's doing it's 13th lap, and don't take any dishes that have a number on them. They have been made especially for someone. 
Although not strictly Japanese, it has become a staple food here, in the same way that Indian and Chinese cuisine has in the West. It's essentially a barbecue indoors, and as such the smoky smell of grilled meat can linger on your clothes after a night out. Vegetables, meat and seafood are available and food is cooked on a grill in the middle of the table. Other dishes such as rice, "bibinba" (a korean rice dish), kimuchi and salads can also be ordered.
Translated literally, this means grilled or barbequed chicken. You pay by the skewer and can choose from a variety of different cuts. Generally, there are two ways to flavour the meat - you can have salt (shio) or a kind of teriyaki sauce (tare). It is usually possible to get dishes such as rice and salad, too. Overall, its a cheap and cheerful way to eat. As an added bonus, there is usually a lively, bustling atmosphere to be found inside. 
Izakayas are one of the best ways to eat in Japan, a kind of combination of restaurant and pub. People often go to eat and drink. The food in Izakayas is varied, so it seems unnecessary to supply a menu. However, there are some chain Izakayas worth visiting. These include (白木屋) shirokiya and (和民) watami. They have pictures, and watami also have a menu available in English
The food in chain Izakayas will not win any awards, and for some, the standard menu available in all restaurants may take the fun out of ordering. However, after a few visits you should be able to find and order dishes you know you like. After this, going to places that have better food but no pictures should be less daunting. Chain Izakayas are good for large groups of people and are generally inexpensive. 
Ramen is often eaten after a night out. It's a form of soup noodles that originated in China and found it's way over to Japan. Usually, the ramen is served with slices of pork, bean sprouts and spring onions.
There are three main varieties. Tonkotsu, shoyuu and miso. Tonkotsu is a heavy, meat based soup that is very popular. Vegetarians should be aware that the stock is made using a lot of pork. Shoyuu is a slightly lighter ramen that has soy sauce as a base, although pork will still be used to make the stock. Miso, the third kind, is made from soy beans. Most shops will specialise in and only serve one type of ramen.