First, regarding Cleon. I think it's important to ask why Thycydides didn't like Cleon. I would argue that it had nothing to do with regret of Athenian Empire, and more to do with the fact that he wasn't Pericles. It is clear to me that Thucydides believes that if Pericles had still been alive, Athens would have won the war. I believe he viewed Cleon as sub-par and undeserving.
Regarding Brasidas, one argument is that he spoke more highly of him because he had more information about him, seeing as he (Thucydides) was exiled to Sparta. I'll be honest, it's been a few years since I read the book and I don't fully remember his accounting of Brasidas, so maybe I need to revisit it.
One important thing you don't mention is his treatment of Alcibiades. He is very harsh on him, treats him as a bit of a rich kid playboy, who uses his charisma and ego to bully the Athenians into the Sicilian expedition in the first place. I would argue that Thucydides blamed the failure of the expedition, and thus the downfall of the Athenian empire, on Alcibiades. This is especially clear to me if you look at how Thucydides treats Nicias, who in many ways was Alcibiades' counterpoint.
For these reasons, I would actually argue that Thucydides viewed the Athenian empire as great, the Melians as indignant peons, and was very sad to see the collapse of the empire.