Algo assim talvez funcione:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
mas como não pode usar um índice, será lento. (Não testei, pode estar errado)
O primeiro
ORDER BY a condição une pais e filhos; então o segundo garante que o pai precede seus filhos; o terceiro classifica as crianças entre si. Além disso, obviamente funcionará apenas no caso que você descreveu diretamente, onde você tem uma hierarquia de dois níveis.
