Edit: @Cawas relata que visualizador do PDF-Exchange realizou a tarefa com sucesso, executando o OCR em um PDF e torná-lo pesquisável.
Para as necessidades que você listou, o PDF é provavelmente a mais simples e a mais multiplataforma. Outra alternativa, um pouco mais obscura, é o formato DJVU, mas ao contrário do PDF, há muito menos suporte para eles, especialmente em termos de OCR.
Há um número de software gratuito de reconhecimento óptico de caracteres disponíveis e fáceis de usar. No entanto, se você estiver procurando por uma solução muito simples, qualquer documento PDF carregado no Google Drive terá automaticamente OCR realizado nele . Há limitações nisso, mas deve funcionar para documentos curtos.