Thanks for asking!
Most linguists agree on the general principle that "all languages are equally complex." That's a very broad notion that's not terribly mathematically specific (in the way that absolute magnitude is.) This doesn't mean that they are always complex in the same ways though. As you mention, the learner's native and target languages are crucial factors in determining how "difficult" learning a new language is going to be. The idea is that a certain level of complexity is necessary for a language to function, for it to be able to express the complexity of human communication needs, but if it gets too much more complex than that level, it becomes too complex to be efficient and it becomes impossible to implement in practice. Because the human brain is equally complex and efficient no matter what language you speak, all languages need to be able to handle the same level of complexity in expression, without exceeding the same limits in processing power.
There tends to be trade-offs in language complexity. A language with very complicated morphology will have much simpler syntax. A language with very strict syntax is likely to have comparatively simple morphology. A language with strict word order doesn't need rich morphology, and a language with rich morphology need not implement strict syntax rules, because those features would wind up being redundant, making the language unnecessarily complicated to the point of being unmanageable.
Some languages are far beyond others in, say, phonetic complexity. Others are phonetically more simple. But, as usual, there's likely to be a trade-off in some other feature. Because the articulatory apparatus of a human being always has the same physiological capabilities and limitations, languages can only get SO phonetically complex before they become unpronounceable, and they can only get so simple before they become unable to express efficiently. A language with more complex phonetics might make up for it with comparatively simple phonotactics--rules governing how sounds may be arranged together.
Any living language is in a state of continual change, and the rules can shift around even on a small scale--from speaker to speaker! This certainly does not help learners.
For any given learner, a target language's difficulty will depend on where and how it resembles or differs from their native language--the starting point will give them both advantages and disadvantages in learning a new system. A language with very similar syntax to your native language, but vastly different phonology/phonetics, will be structurally more easy but a nightmare to pronounce. A language closely related to your own will be more easily interpretable, but will inevitably provide other hurdles. Unrelated languages--like, say English and Japanese--are likely to present more issues because they have so little common ground that there isn't much of a jumping-off point for the learner.
I hope this helps!