acattle's comment that there is a trade-off between inflectional complexity and strict word order is a good answer to your question. I think it would really help to illustrate this with some examples.
First of all, let's look at English word order (actually it's the order of constituents, not words):
Subject Verb Object
The dog bit the man.
The man bit the dog.
English word order is SVO. If you move the object to subject position and subject to object position the meaning of the sentence changes fundamentally. The dog bit the man is not the same as The man bit the dog.
In German, however, you can reverse the order of these consituents without changing the (truth-conditional) meaning of the sentence:
Der Hund biß den Mann. (SVO)
Den Mann biß der Hund. (OVS)
Den Mann is accusative, so although it's in first position in the second sentence, it's still clear that the man/den Mann is the object in both sentences. Word order is free in German in the sense that these two sentences describe the same action. However, OVS word order is marked and might be used to stress the identity of the object, somewhat like It was the man that was bitten by the dog, not the woman.
In German you can move constituents around because they are marked by case. In English you can't, but there are other strategies to do that: It was the man that was bitten by the dog shows two: Passive and it-cleft.
(Other aspects like verb-second word order and the Vorfeld - Mittelfeld - Nachfeld distinction only show that German word order is not completely free - But still it is much more flexible than English word order.)
However, German also has these syntactic options. As a native speaker of German and with some experience in teaching English to advanced learners of English, I don't really see how English discourse structure should be terribly hard to learn for native speakers of German. There are some idiosyncrasies, in the sense that one particular structure is more appropriate in a certain context in English, but another one in German. But you get that with any pair of two languages. What I do think is challenging, particularly for advanced learners of English, are choices in English syntax where there is no hard and fast rule. For example whether to use simple past or present perfect to express an action in the past, or whether to use the of-genitive or the s-genitive/possessive.
Your friends might find English discourse structure challenging for their particular reasons - After all learners are individuals and everybody has their own way of learning a foreign language. Also, I think what you perceive as difficult in a foreign language and what actually is difficult for you can be two very different things (that's my personal experience from teaching - So I don't have any actual data to back this up).