About Cologne:
Food and Restaurants
Many traditional restaurants are located at the center of Cologne, the “Altstadt (Old Town). Here the famous and delicious local beer, known as “Kölsch”, isserved, usually in distinctive small glasses of 0.2 litres, in contrast to Bavarian beer which is often served in big litre glasses.
The Rhineland has its share of food specialties (some more detailed recipes in German can be found e.g. at http://www.wdr.de/domcam/rezepte/ 
and
http://www.koelner-wirte.de/koelscherezepte.php):
Halve Hahn
Translated literally, as"half a chicken", it is in fact only a dark roll made from rye flour, some butter, and a thick slice of medium-old Dutch cheese. Usually it is eaten with hot mustard and gherkins. The origin of the name is unclear.
Kölscher Kaviar
Another misnomer "Kölscher Kaviar" ("Colognecaviar"). It is not caviar but black pudding, served with onions.
Sauerbraten
Sauerbraten is roast beef marinated with vinegar and molasses. It has a sweet-sour taste. Traditionally, it was made of horse meat, but today it is commonly beef.
Himmel un Äd
Meaning “Heaven and Earth”, it combines mashed potatoes and mashed apples, combining fruit from above and from within the earth.
Mussels
Due to the trade connection between the Dutch coast and Cologne, mussels from the North Sea became a favorite meal also for poor people. Traditionally, mussels were only served in months containing the letter “r”, due to cooling problems. Today you generally may get mussels outside the season.
Hämmchen
Everyone knows the stereotypef that Germans eat pig's nuckles with sauerkraut can get it confirmed in Cologne. The knuckle is called "Hämmchen" in Cologne dialect, while standard German calls it “Eisbein”.
Döner and other modern fast food
Although, of course, not a speciality from the Rhineland but from Turkey, today Döner is the most popular fast food in Germany.
Another common fast food is Currywurst (sausage with curry sauce) which, it is said, was invented during the allied occupation. Legends vary with respect to where it was invented and whether it was invented by a British Indian soldier.
Restaurants:
Früh, Am Hof 1 (near the cathedral): A traditional brewery, well-known to tourists, serving the specialties and other food (and beer, of course). Menu in English available.
Malzmühle, Heumarkt: Another brewery with international flair ever since Bill Clinton drank his first Kölsch here in 1999. It is said that he had no money and ambassador Kornblum had to pay Bill’s bill.
Sion, Unter Taschenmacher 5-7 (Tramway 1, 7, 9 station Heumarkt), another traditional brewery. Also king sized sausages are served here.
Bier Esel (Beer Donkey), Breite Straße, (Tramway 1,7,9 station Neumarkt), famous for its traditional mussels.
Other (non-traditional) food:
Joe Champs, Rudolfplatz (tramway lines 1, 7, 9): A restaurant where American style hamburgers are served. NFL games can also be watched on large screens.
Maredo, Heumarkt (lines 1,7,9): Restaurant for South American beef steaks.
Of course, the international fast food restaurants are well represented in Cologne, listing them would exceed this site.