Lo que pasa es que un order by es de esas intrucciones que para esa cantidad de registro prefieres evitar...
Order by, debido a su naturaleza, hará que tu Query sea mas lento
Mira, si la verdad no tienes mucha "libertad" para programar y optimizar tu aplicación, pues muéstrale al/los usuario(s) lo que pasará al ser tan restrictivos.
Soluciones hay, pero que no puedas implementarlas... nada que hacer
Saludos
