My guess is that, in many cases, agency (as in, the capacity to act and make choices) is a manifestation of the observer's inability to explain and predict the agent's actions.

This is my guess too. Agency, intentionality, free will, etc. to me are all cases of the Kolmogorov complexity of the agent being higher than the Kolmogorov complexity of the goal, so we (meaning 'we primates, we humans') tend to assign a mind to the agent, just as we do with our peers.