До сих пор как-то не догадывался, что загрузка страницы может существенно тормозить из-за большого количества SQL-запросов.
Однако, удалось уменьшить скорость загрузки главной страницы до 10 раз за счёт кэширования ленты новых мессаджей - генерации кода только если сообщение было добавлено (во время генерации страница по-прежнему будет грузиться дольше).

А какие ещё способы оптимизации PHP и работы с MySQL можно использовать?

Советуют базу правильно индексировать, например, но я такими тонкостями, в общем, не заморачиваюсь.

Насколько тормознутый сам движок PHP, например? Вроде как сложность кода не должна существенно влиять на скорость работы скрипта?

Наглядно отследить сложно, т.к. время выполнения скрипта варьируется случайным образом даже на локальной машине.

p.s. Интересно, как работают движки-дуры с огромным количеством кода и запросов? Работают ведь как-то...

mysql_pconnect
индексы в базе *важней всего*
кэширование контента
если сервер а не хостинг то тюнинг mysql сервера