There are many SOV languages, including Japanese and Turkish. In fact, SOV is the most common word order, followed by SVO and after a gap VSO.

The thing about German is that it can be both but the word order isn't free either, as it is in Latin, but there are rules that aren't straightforward at first glance. So short sentences often have SVO with a 1:1 translation to English but the more complicated the sentence, the more often you have SOV, especially when you count the content word and not the auxiliary. I can go into more detail how this so called "verb second" works if you want. But I think that that's where the frustration comes from: easy sentences are intuitive and then – boom – out of the blue it changes.

Also: German is a Western European language so English native speakers are more likely to come into contact with it.