The Republic wasn't democracy, but points along the political cycle he sketched were democratic (though surely Plato wasn't thinking of anything as specific as parliamentary democracy as we know it today.)
The young Marx would have said that democracy (though not anything as specific as parliamentary democracy as we know it today - more like free association, cooperation, and individual autonomy) expressed the truth of human nature, while the old Marx would say that human nature plus the path of technological development existing over our whole history implies that at a certain point something like parliamentary democracy would be inevitable (but not irreplacable.)
I often hear people speak of democracy as the next, or the final, inevitable stage of human social development. Its inevitability is usually justified not by describing power relations that result in democracy being a stable attractor, but in terms of morality - democracy is more "enlightened". I don't see any inevitability to it - China and the Soviet Union manage(d) to maintain large, technologically-advanced nations for a long time without it - but suppose, for the sake of argument, that democracy is the inevitable next stage of human progress.
The May 18 2012 issue of Science has an article on p. 844, "Ancestral hierarchy and conflict", by Christopher Boehm, which, among other things, describes the changes over time of equality among male hominids. If we add its timeline to recent human history, then here is the history of democracy over time in the evolutionary line leading to humans:
There are two points to observe in this data:
I do believe "progress" is a meaningful term. But there isn't some cosmic niceness built into the universe that makes everything improve monotonically along every dimension at once.