Cool, muy elaborada tu respuesta, pues creo que si, hay una tabla centrál que debe tener varios millones de filas, las demás no tienen tanto. Lo peor de ello es que de esos varios millones en muchas ocacioens no busca en índices.
También depende mucho el alcance de tus datos al hacer los querys. Así sea una tabla de miles de millones de registros, si necesitas datos recientes deberías empezar por ordenar los resultados de forma descendente. Y después, de asegurarte sólo de regresar los registros necesarios. Es decir, usar limites (clausula limit) dentro de lo que sea posible.
Dudo mucho que usar NoSQL sea una solución viable a usar en poco tiempo, ya que contiene otra lógica y forma de estructura y entonces tendrías que cambiar la obtención de los datos en la mayoría de procesos. A menos que, en toda la aplicación uses llamadas tipo REST y que tus procesos ya tengan definida una estructura gral de salida que sea con la que trabajes (en este caso, sólo quedaría armar tus base de datos NoSQL de la misma forma). Pero por lo que dices, casi estoy seguro que revuelves PHP con HTML y demás cosas.
Sobre PHP, podrías empezar por crear estadísticas de cuanto lleva cada proceso. Aunque aquí la mayoría de problemas viene de crear ciclos infinitos o muy pesados para tareas muy simples, de sobrecargar variables ocupando mucha memoria y de crear ifs anidados enormes sin mucho sentido.