Noget som dette kan måske virke:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
men da den ikke kan bruge et indeks, vil den være langsom. (Har dog ikke testet, kan være forkert)
Den første ORDER BY tilstand sorterer forældre og børn sammen; så sikrer den anden, at forælderen går forud for sine børn; den tredje sorterer børnene indbyrdes.
Desuden vil det naturligvis kun fungere i det tilfælde, du direkte beskrev, hvor du har et to-niveau hierarki.