Is language really too complex for children?

You misstate the crux of the so called "poverty of the stimulus" argument. It does not say that language is too difficult for children because it obviously is not. The point is that even with remarkably impoverished stimulus (with some very few extremes like feral children being the exception), children seem to acquire syntactic structures for which they simply did not receive enough input to form meaningful generalizations.

This argument has been attacked from many angles, some from misunderstanding but others, in my view completely convincing.

1. A lot of argumentation is about whether children don't really receive a lot more implicit instruction in grammaticality. And that's certainly true. But the POtS argument does not dispute that. It merely says that even with almost no such stimulus, children still acquire those structures. It also says that the sort of linguistic nurturing we take for granted is not at all common across cultures which still does not inhibit acquisition. So this is the one part of the argument that stands.

2. A more successful attack is that on 'learnability'. This argument says that for POtS to stand, we would need some objective concept of learnability for each structure. Something that would quantify how much exposure to natural language a person needs to learn something. And not even a hint of that is offered by POtS proponents. Moreover, many of the claims on exposure have been challenged by corpus analysis. Of course, just because we can't specify learnability in a falsifiable way, it does not mean it does not exist. Samson wrote a whole book punching holes in this concept.

3. Another challenge (my favourite) is that universal grammar does not really represent much of what language is. It's a handful of rules (more or less disputed by linguists) of limited relevance to communication. Let's just look at the awesome amounts of language a child has to learn that UG has nothing to say about. Thousands of words, each with incredibly complex usage rules. A child has to develop judgements about register, social appropriatness, dialect, etc. So there's a lot to learn and it's obviously not too much. But if you were to write it all down, it would fill volumes. So why are a few relatively simple structures such a standout? Isn't more likely that we're missing something about how they're acquired than needing to posit a whole new universe of hard-to-prove innate structures?

4. But the killing blow was dealt by Thomasello and researchers in his tradition. Most convincingly, research by Ewa Dabrowska showed that children really don't acquire the troublesome stuctures in the same way that Universal Grammarians imagine. They acquire things like recursion only partially and are not at all able to generalise to more complex instances. In fact, this variability persists into adulthood. Ability to process complex recursions varies by how much exposure one has had to language in which they often appear.

So the answer to the question "What exactly is it about language that should be too complex for children?" is that on the surface almost everything should be too complex but in reality almost nothing is. The only things that are too complex, are those that not everyone can learn or not learn equally well. But those depend on a combination of availability of input and generalized (rather than very specific) ability.