I have never been able to get away with just saying "it depends"

I have: "Зависит." Everyone understands that very well.

There is no word that means "complexity", but can not be alternatively understood as "difficulty".

Kinda. "Запутанный", "навороченный", etc. Besides, just as any language, Russian depends on the context. In some context the word "сложный" will be understood as "complex", and in other context -- as "difficult" and that's fine.

But to your complaints about expressing certain concepts in Russian I would add the observation that the Russian language has no word for "privacy" -- none at all.