Possivelmente, As Joias de Aptor , de Samuel Delaney. Existe um artigo da Wikipedia sobre a história aqui .
O protagonista é Geo e ele está viajando com uma sacerdotisa. A cena com o edifício é:
The building they suddenly came upon had tongues of moss licking twenty to fifty feet up the loosely mortared stones. A hundred yards from the water, the jungle came right to its edges. The whole edifice had sunk a bit to one side in the boggy soil. It was a far more stolid and primitive structure than the barracks. They scraped and hacked in front of the entrance where two great columns of stone, six feet across at the base, rose fifty feet to a supported arch. The stones of the building were rough and unfinished.
E a estátua dentro do prédio:
Behind a twisted metal rail and raised on steps of stone, the ruins of a huge statue sat. Carved from black rock, it represented a man seated cross-legged on a dais. An arm and shoulder had broken off and lay in pieces on the altar steps. The hand, its fingers as thick as Urson's thigh, lay just behind the altar rail. The head was completely missing. Both the hand still on the statue and the one in front of them on the steps looked as though they had once held something, but whatever it was had been removed.
Mas os protagonistas viajam de navio não voando. Além disso, o prédio não emite fumaça, embora algumas páginas antes tenhamos:
Twigs and rubbish littered the metal floor. They walked between double seats toward a door at the far end. Effaced signs still hung on the walls.
N .. SM .. K .. G
que, se você realmente esticá-lo, pode ser letras misteriosas relacionadas à fumaça.