I believe difficulty should be provided. In cases of a puzzle like my tizowyrm or your fimbulvetr, when both the word is difficult and only a very small group of people is likely to have heard about that word, it's only fair that the guessers are warned that they will most likely not figure it out
As for long phrases, they usually have more repeating letters, so guessers have a sense of accomplishment. They also have more various letters, so the in puzzle-in alphabet ratio is better, making the puzzle easier