My native tongue is French, so in my case it was Rabelais' "Gargantua" (~1500) and "La Chanson de Roland" (~1100). Both books require some motivation to get used to their respective languages. After a while, I could read almost fluently Rabelais' prose ; it was immensely funny, coarse and impudent. Roland was harder to grasp, I had to use a specialized dictionary, but it's a concise and epic tale, and I read some verses so many times I ended learning them by rote.
Even translated, some short books from a very different culture far in the past can be challenging. For instance "Eugene Onegin" or "Gilgamesh". As a counterpoint, "The art of war" is an easy read, though written 2300 years ago in a small kingdom of China.
A last comment: the author conflate books that are difficult because of a technicality in their writing, and those that are strange in their story. The translations of Abe Kobo or Kafka I've read had nothing difficult in their words, but the surrealist plots were very unsettling. In "Pedro Páramo" the reader feels lost in a harsh world and unsure of reality. Meanwhile, Perec's "La disparition" or Becket's "Molloy" are more about style tricks.