Något liknande det här kanske fungerar:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
men eftersom det inte kan använda ett index, kommer det att gå långsamt. (Testade dock inte, kan ha fel)
Den första ORDER BY tillstånd sorterar föräldrar och barn tillsammans; sedan säkerställer den andra att föräldern går före sina barn; den tredje sorterar barnen sinsemellan.
Dessutom kommer det uppenbarligen bara att fungera i det fall du direkt beskrev, där du har en hierarki på två nivåer.