A potential solution to this problem is to choose a native language that
is not a language of anybody in the country (e.g. Canadian native people
could choose Nahuatl) or something like Chinook Jargon, that is of
native origin but is not the language of any particular group.
On the issue of difficulty, it is certainly true that it is hard to
measure difficulty, that a lot depends on what you already know, and
that a language may be easy in some respects and difficult in others.
However, I suspect that there are some features of a language that
make it objectively difficult for adult learners whose first language
is anything other than a fairly closely related language. Admittedly,
Algonquian morphology is not trivial, but from what I know of it, it
is not nearly as complex as Athabaskan. Insofar as other aspects of the
languages are comparable, as I suspect in this case, my impression is that
Athabaskan languages are considerably more difficult to learn than
Algonquian languages. A bit of evidence in support of this, admittedly
far from conclusive, is that non-natives seem very frequently to have learned
to speak Algonquian languages, especially Cree, whereas they only very
rarely learned to speak Athabaskan languages, in what appear to have
been similar circumstances (e.g. the fur trade). So I suspect that
to some extent we can talk about the relative difficulty of learning
languages.
Bill