Arieccomi!
L'idea di usare UNION é molto buona, solo che cercavo qalcosa che potesse essere più "integrabile" al codice che ho fatto, per evitare di stavolgere tutto.

Dopo giorni di ricerca ho trovato proprio quello che cercavo:

Codice PHP:
$query = "(SELECT * FROM tabella, CASE citta WHEN 'Barletta' THEN 0 WHEN 'Trani' THEN 8 WHEN 'Bari' THEN '65' ELSE 10000 END ORDER BY citta )"; 
Penso sia molto più performante!
Ovviamente, per velocizzarlo, al posto del nome città, ci metto una chiave numerica. Funziona che é una meraviglia.

Ho trovato la soluzione su Google Gruppi