Additionally, in the last few years though there's been a bit of foodie revolution; Kex hostel has some pretty solid dining at their in-house restaurant, and there are a number of 'American New' places sprouting up, both diner- and pub-style.
Anyway, I agree, Iceland was magical. The people were so, so great, the country was gorgeous and full of history, and (for my money) the food wasn't half bad.
That's the restaurant where my friend worked...though he has moved on.
Second the recommendation here.
So our food experience was good, but agree - the experience was incredible. Without a doubt the best day of my travels anywhere in the world was our Golden Circle tour from Reykjavik - 6 friends, great tour guide, drinking chilled vodka in a hot spring while it snowed on us.
I live in Iceland. The trick is to either prepare your own sandwiches or eat something else.
http://fiskmarkadurinn.is/ completely changed my mind about eating Fish and is still the best salmon I've had in my life.
Also probably the best Thai restaurant I've ever been to was in Reykjavik and I live in New York in a neighborhood famous for its Thai restaurants...