How can one distinguish between an AI and a "sufficiently advanced algorithm"?
As you correctly pointed out, people tend to misinterpret the expression AI since they do not know what's behind an AI; it is pretty clear that in AI there is no more than just a bunch of algorithms and flowing bits. Talking about the nature of an AI without talking about the algorithmic paradigm of that AI is pointless and antiscientific.

This point of view is quite cynical; what we call intelligence is just the capability of solving particular problems.

The quote you cited in the title it's a derived version of the quote below, by a science fiction writer.


  Any sufficiently advanced technology is indistinguishable from magic. - Arthur C. Clarke


Hence I doubt that a scientific answer exists since science lacks a formal definition of sufficiently advanced algorithm and advanced algorithm.