Vikings being vikings: a reenactment at Iceland's annual Viking Fest.

Iceland – remote and north of most of the rest of Europe – was first settled just over 1,000 years ago by Norse Viking men who brought Celt women as sex slaves.

Reykjavik's Hallgrímskirkja, the largest church in Iceland, with Leif Ericcson statue.

This historic tidbit that you learn at Reykjavik’s Saga Museum, along with tales of burning women at the stake and gruesome executions, shows Vikings as a rough-and-tough people. Their other museums, events, tall stature, impossibly long, healthy hair, and cuisine of the metro region highlight Viking descendants to be a studly bunch. They even have a letter in their alphabet – ð – that looks rather phallic. Icelanders are proud of their heritage.

Where to stay. When traveling in Europe, it’s often hard for Americans to duplicate the comforts of home in a hotel. That’s definitely not the case with Hotel Holt. You’ll see Colgate in the spacious bathrooms with bathtubs. Fluffy spa robes, clothes steamers, flatscreen televisions and Icelandic breakfast treats make travel much less wearing. Their happy hour – and phenomenal liquor collection – seem to attract all of professional Reykjavik.

Where to eat. Really, you don’t hear a lot about the cuisine of Iceland in the States, but you should. From high-end to street food, Icelanders have perfected the use of the bounty found in their micro-climate.

It may be difficult to pronounce "grillið" in Icelandic, but it translates into "barbecue." Near the downtown airport, in the Radisson Blu Saga Hotel, is Grillið Restaurant. They use accessible Icelandic ingredients in inventive, cool ways. Think lamb tartare – raw meat doesn’t scare Vikings – with sour cream, breadcrumbs and fried minced kale; or Icelandic prawns with cod mousse, lumpfish roe, lemon and rose pepper sorbet, arugula, nasturniums and avocado cream.

With other hot dog stands all over the city, selling products that look identical to the naked eye, why do people only line up day and night for Bæjarins Beztu Pylsur?

People whisper that this guy’s hot dogs are cooked in beer. Others shrug that they're exactly the same as all the other hot dog stands; it's just marketing. Cab drivers, city employees and everybody in town laughs about how the guy who owns the stand is making money hand over fist. Anthony Bourdain, Madonna and even Bill Clinton have eaten there... Clinton, presumably, before adopting a vegan diet. At the risk of sounding like Beavis and Butthead: hot dogs. That adds to the studly theme!

"Everyman" sculpture in Reykjavik.

Fiskfélagið means "Fish Company" in Icelandic, but there’s a whole lot more to this really cool, global cuisine restaurant. It’s located in a basement of a stone building; though it has a goth-like vibe, people of all ages and walks of life love going here. With their prix-fixe menus, you choose from Icelandic or world recipes, ranging the gamut from Argentinian to Faroese dishes. Presentations include molecular gastronomy and authentic ingredients from each area.

DILL is located within The Nordic House, right outside Reykjavik's historic downtown. Celebrating all Nordic countries, the Nordic House is a cultural complex including library and art gallery. DILL has serene water views and of the airport. The restaurant gets its veggies and herbs from a garden right on site. Even the smallest elements are given exquisite attention: homemade Icelandic sea salt is part of the bread service. The beauty of the freshest herbs, vegetables and fish is something that's hard to improve upon.

Now, if you’re looking for manly and studly in a meal, there’s no topping Reykjavik's 3 Frakkar: Chef Úlfar Eysteinsson is famous for his ideas with traditional foodstuffs. I tried an ancient dish that even the native Icelanders veer away from: fermented shark. Potted, fermented shark was how Vikings preserved the meat, though some food anthropologists say that other preservation methods were available to them. They liked it! You eat a bit on a toothpick with a cold shot of Brennivin, an anise-like schnapps sometimes called "Black Death."

One might really need a full bottle of it: Anthony Bourdain pronounced fermented shark one of the absolutely grossest things he ever ate. How did I find it? I flung my toothpick across the table in outrage!

Whale penis on display at the Iceland Phallological Museum.

Then, I tried little tastes of things on an appetizer plate: reindeer pâté with lingonberry syrup was a stronger, country pâté, rich and still accessible. Smoked puffin – those fat little birds that resemble penguins – the flavor was tasty, like smoked beef, but the texture got to me. They are very, very fatty and their mouthfeel is quite gelatinous. After that, I was relieved and eager to try raw whale sashimi. If nobody told you differently, you’d think it was the reddest, most flavorful tuna sashimi you ever had. I finished the portion!

What to do. If you really want to learn about being studly, why not just get to the point, so to speak? The Iceland Phallological Museum, better known as “The Penis Museum,” started as one guy’s weird personal collection. He got a gift of a bull’s penis as a kid and things took off from there. The unofficial saying for many years was “every kind of penis except one (man)”. That is, until one geezer who thought himself quite the lothario in the day wanted to memorialize his manhood: he bequeathed a very personal donation in his will.

In the suburb of Hafnarfjördur, just a short bus ride from Reykjavik (and gloriously, their buses have WiFi), is the Viking Village. Think of it as an ancient Viking resort! There’s a traditional hotel, along with the type of shared longhouses and little cabins the Vikings used to snuggle up in... along with a group hot tub. They have a restaurant and pub serving Viking foods like lamb soup and also, familiar bar foods.

In June, they host a Viking Fest with a lot of very tall men who look like Robert Plant (top) doing their ancient manly thing: roasting meats, fake fighting, selling leatherworks, teaching the young ’uns to do the same.