If you want to try Minke Whale and Puffin, you can get both of these in small portions at Tapas Barinn (The Tapas Bar), which serves them alongside more traditional Spanish tapas. You should also try the lobster soup at Sægreifinn, which come highly recommended (I'm not a big seafood fan but everyone I know who is and has tried it recommends it).
Harðfiskur (dried fish) and hákarl (putrefied shark) are both served (again in small portions) as part of the Icelandic Braveheart Breakfast at Café Loki opposite Halgrímskirkja, the big church you can see from almost the whole city. They are served with some delicious rye bread and a shot of Brennivín - hair of the dog if you've had a hard night. Their menu also includes other traditional Icelandic food.
The BSÍ Bus Terminal (where your bus from the Airport will arrive in town) has a café that serves Svið - boiled sheep's head. You can also buy a lot of traditional food in the supermarkets.
And if you really want to go to town, figuratively speaking, you should visit during the month of Þorri and attend a Þorrablót, where they serve everything from ram's testicles to blood pudding, and more.
And finally, the far more accessible Skyr, the local yoghurt (debates still rage about whether it IS actually a yoghurt) comes in many flavours and can be bought from any supermarket in individual portions.