First of all, when people--especially Western people--think about learning a foreign language, they usually think of the major Western European languages, and these are, besides English, the FIGS languages: French, Italian, German, and Spanish. Except for German, all of these are Romance languages, and the Romance languages are all essentially simplified Latin: Different forms of local vernaculars which derived from Latin but have undergone centuries of simplification to streamline their grammars. German, meanwhile, has retained a relatively complex grammar system which includes three grammatical genders (the Romance languages listed have only two (Latin has three, but Romanian is the only major Romance language today which retained these), and English has none for most nouns, inanimate objects generally being simply an "it" in English) and four cases, which can be quite a shock for English speakers who are not used to dealing with grammatical cases, as English hardly uses them except in pronouns--for example, the difference between "he", "him", and "his". Combine this with the German tendency to put main verbs at the end of a sentence if the sentence uses a modal verb (for example, a German would say "Ich habe das Buch gelesen", i.e. "I have the book read" rather than "I have read the book"), a practice which I have seen English speakers describe as feeling like "talking backwards", and you have a grammar which, at first glance, may seem intimidating to people whose first choice of a foreign language is typically either French or Spanish.
Despite these features, the truth is that German is still one of the easiest major world languages to learn when you look outside of Western Europe. All Slavic languages (like Russian, Polish, and Czech), all East Asian languages (like Chinese, Japanese, and Korean), all Uralic languages (like Hungarian, Finnish, and Estonian), and most other world languages from Arabic to Zulu are vastly more complex than German in terms of their grammatical structures; most of them have even more cases than German's four, and many of them have such complicated writing systems that just learning the mechanical process of how to read and write them, much less understand what those written symbols mean, is a task which dwarfs the process of getting used to German letters like Ä and Ö. As someone who grew up in a Finnish family and has suffered through trying to learn Russian grammar rules, I can assure you that even if German's grammar rules are more complex than those of English or French, most people in the world live with grammar systems which are orders of magnitude worse.
But a language is more than just its grammar. However many grammar rules you might need to learn to speak a language fluently--and there might be dozens or even hundreds of them--the single biggest task of learning a language is always memorizing the vocabulary. To speak a language fluently, a baseline for most languages is a vocabulary of 3,000 words, and memorizing 3,000 words in any language is not easy. Even once you get to that point, my experience has been that you can't really converse with people comfortably with a vocabulary of 3,000 words; you can probably express most things that you need to say in everyday life, but if you want to have more personal conversations about more abstract subjects, that kind of a functional vocabulary just won't cut it: You need to be able to express subtleties with your language, and a fine touch for a language (what Germans call "Fingerspitzengefühl", literally "fingertipfeeling") is something which takes years and years to develop. As I've written in the past, long after you've gotten used to the grammar rules of a language, your inability to express what you want to express because of missing words in your vocabulary will continue to trip up your efforts to communicate. There are many words which you have rarely heard in your native language, and it is unlikely that you have ever heard these words in any foreign language you might be learning.
Here is where one of German's most intimidating features actually makes it, in my opinion, one of the easiest major languages to learn: The tendency to build compound words. People who begin learning German are sometimes intimidated by the presence of words like "Kraftfahrzeugzulassungsstelle" in everyday German, and wonder how any human being could ever remember what words like that mean. Once you start learning German, however, it becomes simple; if you are a native English speaker, how difficult is it for you to understand the word "motorvehicleregistrationoffice" (a rough literal translation of "Kraftfahrzeugzulassungsstelle")? That is not an English word because English spaces out nouns like that into several words, but even though you have never seen this word before, you can easily understand what it means. German is the same way: It simply takes "phrasal nouns" like this and combines them into one word so that it is clear that that whole string is one entity. Once you begin learning individual words like "Kraft" (power) and "Fahrzeug" (vehicle), it's not difficult to piece words together and make one long word, or to pick those long words apart into their separate components. You can even start doing so yourself; Germans sometimes freely coin their own words by putting different words together, and other Germans will immediately understand what these "Kunstwörter" (artificial words) mean.
The result of this, in my opinion, is that German becomes relatively simple to learn in the long run, because it simply contains fewer morphemes, or rather fewer lemmas, than other languages. A morpheme is the smallest part of a language which contains individual meaning; for example, the word "streets" contains two morphemes, namely the noun "street" and an "s" on the end to signify that the word is the plural form. A lemma, meanwhile, is simply the basic form of a word: Not a plural, not a participle, not conjugated, just the basic dictionary form of a word. For example, the English word "walk" is a lemma, and from this lemma stem many other words: "walks", "walking", "walked", "walker", and so on. It also exists in compound word forms like "sleepwalking" and "sleepwalker". These words are fairly easy to remember, because they combine two common English words ("sleep" and "walk") together. They are thus much easier to remember than the sometimes-used terms "somnambulism" and "somnambulist", which mean the same things but which most native English speakers prefer to avoid because they are simply harder to remember and use.
Here is where German's tendency to build compound words makes it easier to learn than most languages which feel the need to coin a catchy new word for every concept that they come up with. People often criticize German for being clumsy and inelegant because of this tendency, but let's be honest, it's just plain easier to remember nouns that describe exactly what they are rather than words which are invented that have no semantic connection to the concepts they portray. There is a certain aesthetic motivation to invest new words which are short and "cool"-sounding, but this has the side effect of forcing people to learn more words when they want to learn a language.
English exists between two worlds: Although categorized as a Germanic language, more than half of English words are actually either French or Latin in origin. French is often seen as the world's most chic* language, and this status comes with a certain pressure to invent cool neologisms in this way. One of the most prominent examples in the modern world was courriel, a portmanteau of "courrier électronique" (a literal translation of "electronic mail") which was invented in response to the idea that saying "e-mail" like every other language in the world would be too detrimental to the status of French as a stylish, independent language. (Interestingly, this neologism was developed in French-speaking Canada rather than in France, as French Canadians are more defensive of their language's position than actual French people in France.) Despite this, French often follows other languages in terms of changing usage. For example, when the record player was first invented, it was called a "phonograph" in English and many other languages (which itself is a coined compound word made from Greek morphemes), but at some point in history, this term faded out of usage and became replaced with "record player". Astonishingly, even French followed this shift: Today, the device is typically known as a "tourne-disque" (literally, "turn-disc") in French, though it was once known as the "phonographe". Despite this, the large number of French loanwords in English speaks to the French tendency to come up with catchy words which English then freely borrows, as English has long been a global language with a desire to seem up-to-date.
* Many will be quick to point out that "chic" itself is a loanword from French, because English didn't contain a word cool enough to communicate this same idea. There is a certain irony in the fact that French probably borrowed this word from the German "Schick".
German generally lacks this urge; German is the most conservative of major Germanic languages (probably second only to Icelandic in this regard), meaning that it has still retained many of the words and forms that it had hundreds of years ago, which is part of the reason why it still has three genders and four cases while these features have been mostly stripped out of English and greatly simplified in Dutch. For example, when speaking the names of numbers, German still names the digit in the ones position before the digit in the tens position; thus, for example, the number 21 is "einundzwanzig" in German, literally "oneandtwenty", which was once the norm in English--as can for example be seen in the reference to "four and twenty blackbirds" in the nursery rhyme "Sing a Song of Sixpence"--but which has long since been discarded in English for the more logical practice of reciting each digit of a number in order. This means that for all of the oddities which German retains, it hasn't formed a lot of new words in the last few hundred years, and has dealt with the need to coin neologisms by just making compound words out of existing German words.
The one thing which really made me realize how important this effect is even in modern-day German was when I realized how Germans handle the Duden. Konrad Duden was a German philologist whose name is now synonymous with the authoritative dictionary of the German language, which is simply known as "der Duden", a name which is used similarly to how Americans might mention looking up a word in "Webster's". The thing about the Duden is that it's not just a book, but a set of 12 volumes, including the Grammatik (a grammar reference), the Herkunftswörterbuch ("origins word book", an etymological dictionary), and the Synonymwörterbuch ("synonym word book", a more common German word for what English speakers call a thesaurus, although German does use "Thesaurus" as a loanword too). What English speakers usually think of as a dictionary, namely a book which provides the meanings of words, is the Duden Bedeutungswörterbuch: "Meanings word book", the volume which actually defines the words of the German language. It might not seem so strange to have all of these different books (after all, English also has separate dictionaries and thesauruses, along with manuals of style and other counterparts to resources found in the Duden set), but what is really unusual about German is that very few Germans actually have the Bedeutungswörterbuch. Whereas American households typically have either a Webster's dictionary or an Oxford English Dictionary and think of these as resources to describe the meanings of words, I have never seen a German in possession of the Duden definition book; everyone who has a Duden book just has the first book in the set, which is called the Rechtschreibung (literally, "correct writing") and provides no definitions, but rather provides the different spellings for words, such as plural forms and female forms (many German nouns have separate male and female forms, such as "Lehrer" for a male teacher and "Lehrerin" for a female teacher). Rechtschreibung is a big deal in Germany: You want to make sure that your writing is correct, but when I realized that no German I've ever met actually has a copy of the definition dictionary, it struck me that Germans do not seem to feel a need to think about the definitions of their words; they know what their words mean, they're just more worried about misspelling unusual forms of those words, and that's the only reference they feel the need to have on hand.
Now, I don't want to read into this fact too much. The fact that the Duden definition dictionary exists suggests that someone is using it, or at least certainly that someone found it important to make one, but I have never actually seen a situation in any German discussion where any German has ever struggled to find a word for what they want to describe or wondered about the definition of a particular word; words mean what people intend them to mean, and it is more important to understand a person's specific intent with a particular word or set of words than to fight over what the dictionary thinks a word should mean. Rather than criticize people for using a word in a different sense from what the dictionary defines that word as meaning, German people discuss their intentions using complete sentences instead of resorting to buzzwords, and this provides a better understanding through more thorough communication.
Okay, admittedly, the observation about the Duden is more anecdotal than conclusive, so to add some data to the argument, there have been studies which measure the average frequency of words in various languages. The methodology is not particularly difficult, it just involves a lot of data: First, you gather a collection of a large body of text from various sources in a particular language. Next, you make a list of all words which appear in these sources. Finally, you create, for each word, a count of how many times that word appears in the collection of texts; typical for such studies is a measure of the IPM (instances per million) of each word. Words with a higher IPM count occur more frequently in the language, and if a particular language has a higher average IPM for all of its words language-wide, then that language is, at least in theory, easier to learn than other languages, because it uses the same words more frequently in everyday use, whereas languages with lower average overall IPM counts are more difficult to learn, because they employ a broader vocabulary in everyday use. In such studies, German consistently ranks higher than most other popular languages in average per-word IPM counts, which means, again, that German reuses the same lemmas rather than employing new or different ones. And that, in theory, makes German an easier language to learn in the long run.
I've heard it said that learning German is like a pyramid: A pyramid is widest at its base, and so when you are getting started at the bottom, there is a lot to take in at first, and it may seem overwhelming. Once you get a grasp of the foundation of the language and begin moving upward, however, the new material which you need to learn begins tapering off, and by the time you get to the advanced levels, there is not much left. I am not sure how true this is, but I think, at least, that it is not entirely untrue. Because the single biggest part of getting fluent in a language is learning the vocabulary, it seems logical that a language with fewer lemmas would be easier to learn, and because German seems to have fewer morphemes and lemmas than more "innovative" languages that like to constantly create new words because people get so bored with their languages that they have nothing better to do than make up new words for concepts that they already had words for, German is an easy language. But then, that's just my opinion, and no one ever learned a language by reading my opinions.