Du musst doch (für's erste) einfach nur je einen Index auf jede Spalte setzen, die in WHERE oder ORDER vorkommt.
Anschließend würde ich noch ein aktuelles
MySQL 5 nehmen und schauen, dass man wirklich nur die Datensätze holt die man braucht.
Wenn der Server dann einigermaßen Ressourcen besitzt, ist da nicht mehr viel zu machen, bei so einer simplen Struktur.
Liebe Grüße,
Valentin