Don't be fooled, the only time someone eats sheepheads and shark are at the "Thorrablot", annual festivals in january/february to celebrate the month of Thorri (according to the old calendar). Then people eat that as well as some other things and drink brennivin. (picture from: http://pannkaka.txt-nifty.com/pp/images/hakarl.jpg)
Icelandic cuisine isn't that much different from other Nordic countries, but more limited to fish, spuds and a limited range of veggies. Add to this some fantastic lamb and reindeer and that's about it. The good thing is that within these limits, Icelanders excel in stuff! Dairy products like skyr (what Dutch would call 'kwark'), local beers and hard liquor ('brennivin') are all well worth sampling!
Oh, another delicatess. My main food source while staying in Iceland, skyr. This is very traditional stuff in Scandinavia, for Americans a quick explain, something between sour cream and plain yogurt. Skyr or kvark or rahka as we say in Finnish, is sour milk product, which is an excellent to use in sweet desserts. Because of its low fat content, it cannot be heated.
Icelandic skyr is the best one. They do it in different flavors like vanilla and strawberry. Low in fat and high in protein. Missing skyr.
Oh, this is so good! The Islandic Ryebread, yummy yummy. Just a thought of it makes me feel hungry. We do bake good ryebread here in Finland, but this Icelandic one is great. It might be because of syrup or sugar, which makes it so sweet kind of, but anyways, oh man it is yummy. Try it. Go to local grocery store and check out labels with Rúgbrauð, guaranteed trip to the world of food.
If you buy french fries ask for cocktail sauce on the side. Almost as compulsory as mayo in Amsterdam. (Picture: http://www.hroi.is/myndir/kokkteilsosa.jpg)