Bergen, Norway dinner with mussels, wolf fish, vegetables, and potatoes...the only thing missing was some lamb or mutton
Louisa asked what carbs I recommend. I did low carb when I started paleo to reduce the excessive amount of bacteria that seemed to cause my IBS. But as I got better I added in more carbohydrates. Personally I enjoy life more with moderate carbohydrate consumption and none of my problems returned. I think low-carb approaches like PaNu are a great approach for losing weight, but I don't think carbohydrates are going to make a slim insulin sensitive individual like me fat. I also think many paleo advocates selectively ignore the large amounts of evidence that roots were important to early humans. I think the best blogs that advocate a sensible approach to carbohydrates for healthy people are Whole Health Source(start with his Kitavan posts) and Primal Wisdom(start with Primal Potatoes).
I do carb cycling. I divide my favorite carbohydrates into rather unscientific categories, trying to rotate them to reduce the odds of me being affected by any antinutrients. My categories are tropical, local winter, and local summer.
The local winter carbs include carrots, squash, potatoes, sweet potatoes, turnips, rutabagas, parsnips, beets, and other vegetables that grow locally. In the winter I often eat a serving or two of these a day.
The local summer carbs include fruits, with a basis towards wild fruits, which I particularly enjoyed in Sweden. When I lived there I would often simply go out into the woods in the morning and gather a basket of lingonberries, sea buckthorn, blueberries, or currants. I think berries can be enjoyed daily in season and more domesticated fruits like apples or apricots with more moderation.
Tropical carbs are more like supplements or treats. They don't grow in New York, but with the Caribbean/SE Asian population in NYC I'd be amiss if I didn't enjoy some plantains, taro, cocoyam, mango, coconut, and other tropical delights similar to what the Kitavans or Okinawans are so healthy eating about once a week or so. Thai coconuts are my favorite because they pack a punch of potassium and it's possible to ferment most of the sugar out of the water.