Zoiets zou misschien kunnen werken:
SELECT *
FROM categories
ORDER BY IF(parent_id, parent_id, category_id), parent_id, display_order
maar aangezien het geen index kan gebruiken, zal het traag zijn. (Niet getest, kan verkeerd zijn)
De eerste ORDER BY conditie sorteert ouders en kinderen bij elkaar; dan zorgt de tweede ervoor dat de ouder zijn kinderen voorafgaat; de derde sorteert de kinderen onder elkaar.
Het zal natuurlijk ook alleen werken in het geval dat je direct hebt beschreven, waar je een hiërarchie op twee niveaus hebt.