I've been staring at this for a few days, and I haven't gotten very far. I've poked into Lucian a little, reading small portions slowly (and I do read Greek very slowly).
To me, his sentences don't seem formulaic. I may be missing what you are talking about, I haven't read much at all outside the New Testament canon and pre-Nicene fathers, but to me, his sentences seem rich, varied, nuanced, sometimes complex and thoughtfully balanced, with careful and precise use of particles.
Now he may be fooling me because I read this very much as a foreigner. But how does a sentence like this strike you?
πολλοὶ δὲ καὶ ἄλλοι τὰ αὐτὰ τούτοις προελόμενοι συνέγραψαν ὡς δή τινας ἑαυτῶν πλάνας τε καὶ ἀποδημίας, θηρίων τε μεγέθη ἱστοροῦντες καὶ ἀνθρώπων ὠμότητας καὶ βίων καινότητας: ἀρχηγὸς δὲ αὐτοῖς καὶ διδάσκαλος τῆς τοιαύτης βωμολοχίας ὁ τοῦ Ὁμήρου Ὀδυσσεύς, τοῖς περὶ τὸν Ἀλκίνουν διηγούμενος ἀνέμων τε δουλείαν καὶ μονοφθάλμους καὶ ὠμοφάγους καὶ ἀγρίους τινὰς ἀνθρώπους, ἔτι δὲ πολυκέφαλα ζῷα καὶ τὰς ὑπὸ φαρμάκων τῶν ἑταίρων μεταβολάς, οἷα πολλὰ ἐκεῖνος πρὸς ἰδιώτας ἀνθρώπους τοὺς Φαίακας ἐτερατεύσατο.
Where do his sentences seem formulaic?
I have only read a handful of pages, I don't see much idiom on those pages. But aren't there some people who write English without much idiom? Perhaps this is simply very formal writing?
I do think very formal writing seems out of place in a novel, at least for modern Americans. But I think this was the first novel, perhaps we have expectations for the writing style of novels that Lucian did not have.
Or maybe I'm simply not seeing things that would be more obvious if my Greek were more advanced.
ἐξίσταντο δὲ πάντες καὶ διηποροῦντο, ἄλλος πρὸς ἄλλον λέγοντες, τί θέλει τοῦτο εἶναι;
http://jonathanrobie.biblicalhumanities.org/