Rome: there's a restaurant on the battlements of the Castel Sant'Angelo.
Best view in the Vatican, and the ravioli is good. Not too expensive, either (at least when I was there).
The Castel Sant'Angelo is definitely worth a look, particularly the old Papal apartments (you have to pay to enter the Castel to get to the restaurant).

London: the Victoria and Albert Museum. Slightly expensive, but the food's good, the museum is brilliant and just look at where you get to eat!


Paris: Chez Marie Madeleine, a creperie near the Pompidou Centre. I really liked their crepes.

Amsterdam: don't know, I've never been.