Algo como esto podría funcionar:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
pero como no puede usar un índice, será lento. (Sin embargo, no probé, podría estar equivocado)
El primer ORDER BY la condición clasifica a padres e hijos juntos; luego el segundo asegura que el padre precede a sus hijos; el tercero clasifica a los niños entre ellos.
Además, obviamente solo funcionará en el caso que describiste directamente, donde tienes una jerarquía de dos niveles.
