Hm. In that case, smaller more frequent breaking changes may also not be ideal. It sounds like no matter how small the breaking change, everyone who uses the library is going to have to update their code... and if it's happening frequently, that could get annoying.
This may be completely off-base, but just going off of what you said about data traversal, would it be completely out of scope for your library to provide a consistent interface for getting/traversing the data it is responsible for? Or do the consumers all use/traverse the returned data in very unique ways such that you couldn't really develop a "general" API of sorts.