База 36 звучит как хороший выбор (при использовании символов a-z и 0-9 это самое большое пространство символов, которое можно легко передать по телефону). Я бы посоветовал вам сделать вывод, содержащий блоки по 6 или 8 символов, чтобы его было легче читать. Также; в конце добавьте контрольную сумму, чтобы убедиться, что в данных нет ошибок.
100 символов в этой кодировке все равно будет непросто прочитать по телефону и получить правильное значение с первого раза. Рассматривали ли вы другой механизм доставки? Текстовое сообщение (SMS)?
В Википедии есть пример кодирования Base36 в Python - не должно быть слишком сложно конвертировать в C #.