Yes, dining in Reykjavik is not as cheap as elsewhere but every meal I have eaten in Iceland has been awesome.

Even in gas stations in the countryside, you can get home-made fresh lunch. Beats fast food any day!

Islenski Barinn, Austurvöllur in front of Althing.
Domo, Thingholtsstraeti near Laugavegur
Humarhusid, on Laekjartorg