The only thing I would ask as a user (and filer of bug 1211, all those years ago) in terms of the interface:
Please don't remove the feature where the first letter of the sort key is displayed in the rendered category page, and if necessary add what it takes to keep it.
There are scripts where this will be a hard problem, but it's still much-used and much-loved in those where it isn't.
- d.