I have always interpreted the passage mentioning Paeon the honey-steward to be saying that the Old Autarch received instruction regarding the succession from someone he knew to be an aquastor of Paeon, his trusted teacher from his youth.
In other words, Paeon is to Old Autarch as Malrubius is to Severian.
This has seemed completely obvious to me since my second reading (which was the first for catching many internal references).
Independently, I'm one of those who doesn't think that the Old Autarch is Appian, precisely for the reason already cited that Appian's name is mentioned as a historical autarch, but the Old Autarch's name is never mentioned in any scene where he is present or even definitely referred to.
I have toyed with the idea that there's some sort of taboo on names of Autarchs during their reigns, but Severian wouldn't have to abserve such a stricture at the time he's writing. Perhaps he has trouble distinguishing the Old Autarch from himself ever since the successional encephelophagy.
In case anyone needs another puzzle to speculate about, it has long annoyed me that Severian describes the Autarch on the counterfeit chrisos from Vodalus as androgynous, which I have (since second reading) always assumed to mean that it's the Old Autarch (the only one since Ymar to take the test in Yesod), yet Severian needs Thecla's memories to recognize the guy as the Autarch when he actually meets him.
-- Dan Rabin