If you want to try svið, go to the cafeteria in the bus station (the BSÍ long-distance station, not the Hlemmur city bus station). Most of the nice restaurants (including the ones I mentioned serving whale, puffin, and the fish buffet) can be found in and around the main shopping street, Laugavegur. The fish buffet is in the Restaurant Reykjavík, but there are lots of other great seafood restaurants downtown and in and around the harbour area. Also, if your hotel or guest house has kitchen facilities, don’t discount self-catering as an occasional option. Bónus is the local discount supermarket (there’s one on Laugavegur), and there you can buy hangikjöt (strongly flavoured smoked lamb), sinnep (mustard), and brauð (bread) to make sandwiches, as well as the aforementioned hot dogs, hákarl, and Brennivín (caraway schnapps). Be sure to pick up a bag of kleinur, which is a sort of addictive twisted donut, for munching during the day.
Sounds kinky.
I didn’t see anyone else mention this, but from the one restaurant I tried (in Corona, Queens), I’d have to nominate Dominican food. I went to an authentic Dominican restaurant, with an authentic Dominican, and it was quite horrible. EVERYTHING was deep-fried. I half expected my glass of water would come out fried.