Поковырялся с сабжем. В общем, решение есть. Возможно — не единственное.

Сначала о грустном: всяческие gocr и ocrad русский текст не жалуют. Возможно, к ним можно найти какие-нибудь патчи, специальные файлы для языка... Я так глубоко не копал. Tesseract тоже не трогал, ибо его нужно «обучать», а я «не настоящий сталевар» и от программы хочу, чтобы она работала без долгих настроек и плясок с бубном.

В итоге остановился на CuneiForm, благо версия для Linux вполне стабильна. В качестве проверки в боевых условиях использовал «Фейнмановские лекции» с торрентов, перегнав предварительно PDF постранично в PNG. Текст распознался прекрасно. Формулы, естественно, идут лесом, но это ожидаемо. Методом тыка выяснилась интересная особенность: если перегонять в монохромный PNG (-sDEVICE=pngmono) — не распознается ни черта, при -sDEVICE=pnggray — отдельные буквы, причем цифры. Зато прекрасно распознается при -sDEVICE=png16m — это RGB, 24 бита на точку... Разрешение во всех случаях было одно и то же — -r300.

Ставил с оверлея sunrise, если кому интересно. Там же есть cuneiform-qt — GUI-морда, от которой лично я удовольствия не получил, поскольку распознавать по одному файлику мне совсем не интересно.

upd: Забыл добавить — требует установленный ImageMagick. Впрочем, мне трудно представить linux-систему без последнего...