In my opinion the biggest name of Brazilian literature in the 20th century is Guimarães Rosa. Unfortunately his language is very difficult to translate (it is difficult and fascinating even to Brazilians).
I'd describe the style as being akin to stream of consciousness, but with a somewhat jumbled sentence structure on top. Of course, I use the term 'jumbled', but I'm sure it's intentional, and it does have a striking effect because of that.
The beginning of the book (first 100 pages) is really hard, mostly because it use words that are not commonly used nowadays but also because some of the words are written as spoken. Some people like to read it loud because of this. I've tried myself for some paragraphs and it really made sense to me :)
To add to this, in Spanish the title is translated so that it loses all sense of being a pun: "La importancia de llamarse Ernesto". "Ernesto" in Spanish has no correlation with "earnestness", it doesn't sound the same as the Spanish concept, and in general, the title doesn't sound like a pun.
Spanish translators often add a footnote saying something like "this is an untranslatable play on words in the original English".
From another perspective -- there is a lyric in the song Shiny, in Moana, going c'est la vie, mon ami. That's not actually English. How do you translate it from English? This line was translated into Russian as c'est la vie, mon ami. Russians can be expected to be familiar with French, at least at this level. Languages at a greater cultural distance -- including Vietnamese -- don't translate it at all. Intriguingly, the line was translated into French as c'est la vie, mon ami. This preserves the meaning perfectly -- it's more accessible to the French audience than it is to the American audience! -- but it completely loses whatever the implication was of saying the line in French as part of otherwise English dialogue.
It's very difficult to translate anything that simultaneously expresses multiple things. You're doing well when you preserve a single aspect of the original.
Part of the problem with Grande Sertão: Veredas is that it is has a very inventive, very oral aesthetics that is based on a local dialect and a culture that is unknown (except very superficially) to most of its readers even in Brazil. The burden on a translator to transfer all of that to the foreign reader is immense.
>Vini, Vidi, vici
>I came, I saw, I conquered.
Notice Latin doesn't require the pronoun I. But literally translating "Came,saw, conquered" sounds like it was written by a petulant 14 year old. Secondly, Caesar's clauses are a nice triplet of two syllables. The English version does pretty well there, until it reaches "conquered," which throws the rhythm off. I said it was a stupid example, because the English translates pretty well IMO, but hopefully I demonstrated the difficult work of the translator.
Off the top of my head, I think these would be tough to translate.
-Shakespeare. Too many puns, and the meter is tied to a rhythm natural to English. All poetry is difficult really.
-Huckleberry Finn. Heavy dialect, which often involves the racial prejudices of the time. How can you translate that part? Nothing will be as disrespectful as the word is in English. Furthermore, how do you translate something like: >It must a been close on to one o’clock Do you preserve the grammar error? What's the difference between "close" and "close on"?
-Faulkner. Same as Twain, plus some very heavy rhetoric.
-Joyce. Same as Faulkner, but more puns, heavier rhetoric. If there's anything harder to translate than Finnegans Wake, let me know.
-Gadsby. This book does not contain the letter E! E is the most common vowel in English, but it's not in many other languages. Is the translator "cheating" if constrains the same letter? Amazingly this problem has been tackled in the translation of a different book, La Disparation, a French novel also without any e's either. The English translation, A Void, avoids the character too. However, omitting the E would be too easy in Russian, so that version doesn't contain any O's.
Fair warning: the book gets a bit dark in parts (he wrote it after his wife's death, and covers that a bit), but not overwhelmingly or throughout.
ETA: To address your original question, Hofstadter's book is organized around the challenge of translating "Ma mignonne", a very tight little French poem by Clément Marot (hence the book title), and goes into great detail about the challenges it presents, with lots of different approaches and translations. He talks about many other significant challenges to the translator -- the one that comes to mind is La disparition by Georges Perec[1] -- a novel famously written without appearance of the letter e. It was translated into English by Gilbert Adair as A Void -- also lacking that most common of glyphs. Other unpublished e-less translations exist, as well.
A few examples come to mind:
Ulysses by James Joyce
Alice in Wonderland by Lewis Carroll
Naked Lunch by William Burroughs
The stream-of-consciousness style of flowing sentences, how the author plays with language, exotic or made-up words, sounds, subconscious associations - all contribute to a very challenging translation, I imagine.
---
Edit: Oh, I'm a couple days late in replying, and others have mentioned similar works of literature.