The only three possible explanations I can think of are

1) Things have radically changed since I last lived there 20+ years ago

2) My view is heavily biased by only having lived in/around Oslo and the rest of the country eats a lot more fish

3) Norwegians eat a lot of heavily processed fish based foodstuff (fish sticks, fish cakes etc), but hardly any fresh fish.

That would probably be point number 2 in your list. West coast and northern Norway eat a lot of fish/seafood. Also within the last 20 years sushi has gotten a lot more popular here, even around Oslo.