"Debt", for me, was one of those life-changing books that completely revised how I think of money and macroeconomics. But I found "On Kings" to be unreadable, deeply mired in esoteric academic theory debates. "The Beginning of Everything" was somewhere in the middle -- it successfully challenged the conventional "Noble Savage" and Lockean views of the emergence of the state. But it was filled with a TON of conjecture, and ultimately made the unsatisfying point that things were very different at different places and times.
I'm sad there won't be any more from him.