Как сделать, чтобы скрипт выполнялся самым первым?
Правильное предположение. Если скрипт все же выполняется не первым, скорее всего, вызывается код, который цепляется к каким то событиям, и ждет их (к примеру, того же построения DOM).
Подключите скрипт перед закрывающим тегом body, остальные подключайте ниже.