Причин несколько и они разного порядка.
Типографика. Да, это был реальный и очень серьезный фактор. В 1879 году Фреге пришлось договариваться с издателем о специальном наборе. Каждая формула занимала полстраницы. Рассел в Principia Mathematica (1910-1913) использовал линейную запись, которую можно было набрать обычным типографским шрифтом. Для распространения идей в научном сообществе это критично.
Композициональность. Линейная нотация тривиально вкладывается сама в себя. Пишешь формулу, берешь ее в скобки, подставляешь как аргумент в другую. У Фреге вложенность означала рост дерева вправо и вниз, что быстро становилось нечитаемым для сложных выражений.
Социальный фактор. Begriffsschrift при жизни Фреге прочитали буквально единицы. Рассел, Пеано, может быть Гуссерль. Книга продалась тиражом несколько сотен экземпляров. Когда Рассел популяризировал идеи Фреге (квантификацию, пропозициональные функции), он уже переложил их в свою нотацию. Большинство логиков XX века знакомились с идеями Фреге через Рассела, а не из первоисточника.
Когнитивный момент. Тут вы правильно подметили про деревья вывода. Двумерность сама по себе не проблема. Проблема конкретно фрегевской нотации в том, что она кодирует логическую структуру формулы (какой коннектив главный, что от чего зависит) пространственным расположением. Это хорошо для анализа одной формулы, но плохо для манипуляции. Когда вы проводите вывод, вам нужно переписывать формулы, подставлять, применять правила. С линейной записью это механическая операция. С деревьями Фреге каждый шаг вывода требует перерисовки всей структуры.
Деревья Генцена работают, потому что двумерность там относится к структуре доказательства, а сами формулы внутри узлов записаны линейно. Фреге же сделал двумерными сами формулы.
Про разницу между двумерностью доказательства и двумерностью формулы - отличное наблюдение, спасибо. Не формулировал для себя так четко.