Какую связку лучше выбрать Nginx+php-fpm или apache+php?
Переехать на nginx в любом случае полезно, но проблему это не решит.
Решение проблемы - оптимизация говнокода. Особенно в SQL запросах.
Nginx сразу ставьте и настраивайте, там делов-то на 20 минут разобраться. Но ищите где у вас образуется узкое место, может apache не виноват.