Něco takového by mohlo fungovat:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
ale protože neumí používat index, bude to pomalé. (I když netestoval, může být špatně)
První ORDER BY stav třídí rodiče a děti dohromady; pak druhý zajišťuje, že rodič předchází své děti; třetí třídí děti mezi sebou.
Také to bude samozřejmě fungovat pouze v případě, který jste přímo popsali, kde máte dvouúrovňovou hierarchii.