How do I sort categories by title while preserving hierarchy?
You should be able to do this with a recursive macro.
Here is a macro alphaList which is passed a list of categories (in alphabetic order). For each category, it outputs that category, and then if that category has any children, it calls itself on an alphabetic list of those children.

To get the children of a category c, you combine descendantOf with descendantDist of 1: craft.categories.descendantOf(c).descendantDist(1)

To get the initial list of top level categories, you use the level parameter: craft.categories.level(1). That will mix together categories from all your category groups, so probably you want to specify the group: craft.categories.group('myGroup').level(1).

{% import _self as self %}

{% macro alphaList(cats) %}
{% import _self as self %}
  {% for c in cats %}
    &lt;li&gt;
      {{c.link}}
      {% set children = craft.categories.descendantOf(c).descendantDist(1) %}
      {% if children|length %}
        &lt;ul&gt;
          {{ self.alphaList(children.order('title')) }}
        &lt;/ul&gt;
      {% endif %}
    &lt;/li&gt;
  {% endfor %}
{% endmacro %}

{% set topCats - craft.categories.level(1) %}
&lt;ul&gt;
  {{ self.alphaList(topCats.order('title')) }}
&lt;/ul&gt;