C++, приоритет операторов

левая часть оператора && должна выполняться первой. Если слева true, тогда выполняется правая часть

Правильно.

если верить таблице, то в первую очередь должна выполняться операция с наивысшим приоритетом

А здесь ошибка.

Приоритет и порядок вычисления - разные вещи. Приоритет, грубо говоря, влияет на воображаемую "расстановку скобок" в выражении.

Раз у && приоритет ниже == и >, то из a() == b && c > d получается (a() == b) && (c > d).

А дальше в дело вспупает порядок вычисления:

very value computation and side effect of the first (left) argument of the built-in logical AND operator && and the built-in logical OR operator || is sequenced before every value computation and side effect of the second (right) argument.

Сначала первая часть до И(&&) потом вторая (в случает если первая true). Данное поведение не зависит от приоритета, а от порядка. Ваша запись эквивалента

if (a() == b) {
    if (c > d) { 
         ...some code...
    }
} 

И тут все выполняется исключительно по прямому порядку выполнения команд