Nem tudo é questão de rodar o OPTIMIZE. Talvez você deva começar a dividir suas tabelas em tabelas menores, normalizar os dados, diminuir as queries, analizar a eficiência das queries (com EXPLAIN), etc.
A primeira coisa que posso sugerir é a de revisar as queries que são rodadas e ver se você precisa de todos os dados retornados. Outra ação possível é começar a expurgar dados antigos da sua tabela, deixando-a mais leve.
Depois o interessante seria você estudar como funciona a normalização de um banco de dados (especialmente deixá-la nas formas normais 1FN, 2FN e 3FN, apesar de também existir a 4FN, 5FN e Boyce-Codd) e ver o que é possível de deixar no seu banco de dados.
Quanto o MySQL, você também pode ver se vale a pena otimizar as tabelas (por exemplo, para InnoDB, mas depende bastante da característica das suas consultas) ou arrumar as configurações do banco. Outra coisa: será que a máquina onde está o banco de dados não está sobrecarregada com outros serviços?
Verifique esses pontos e veja onde dá pra começar.