The crux of the issue is that kanji don't have an inherent "natural" ordering that a user would expect. Sorting by their character code doesn't mean anything to a Japanese person. But, what if we made our own standard of what entails a "natural order". There's nothing about A–Z that makes the alphabet obligated to be in that order (and not something like based on sound or shape) other than it being the convention that developed. Even hiragana can have different orderings (AIUEO vs IROHA [0])
One proposed method would be to do it how the dictionaries do it: first sort by major radical, [1] and then by stroke count. This is something most Japanese learn when learning how to write characters anyway (of course ambiguities would arise when the radical is shared and the stroke count is the same, but we could just choose a third arbitrary factor; we'd also have to decide on a specific written form as stroke count can differ depending on whether it is handwritten or the font).
We could then teach our approach to schoolchildren and it would just become accepted over time like other things they learn. But wait you say, it's more natural for them to sort on pronunciation. However, if I gave you a list of polygon names and told you to sort by the number of sides they had, you'd be perfectly capable of doing it despite that not being alphabetical. Things are less "unnatural" if you grew up learning them and your brain doesn't experience dissonance.
Anyway, just my hot take.
[0]: https://en.wikipedia.org/wiki/Iroha
[1]: https://en.wikipedia.org/wiki/Radical_(Chinese_characters)