OK, let me have a go at breaking down the structure. The sentence could end with apepleusan, right? Lit. "X. & P., having got onto a boat and having put in (it) the things worth most (lit. the things worthy of most, i.e. the most valuable things, their most valuable possessions), sailed off."
(Gen. very common with axios, e.g. ta oudenos axia worthless stuff; axia pollou worth a lot, valuable; axia pleistou worth most, most valuable.)
Now things get a little more tricky. What doesn't emerge from Markos' fine "levels" (all good except in this respect) is that "ws men tois pleistois edokoun" is parenthetical, you can remove it without affecting the construction. Lit. "as they (X.&P.) seemed to most people" i.e. "(as most people thought)" or "(so most people reckoned)". The "men" (without an answering "de") suggests that not quite everyone thought so. The following participle, filotimhqentes ("angered," "pissed off," let's say), does not depend on edokoun. (If it did, it wouldn't be a participle but an infinitive.) Rather the "ws - edokoun" clause is subordinate to filotimhqentes, which is just a participle continuing the sentence: "... they sailed off, angered (as most thought) ..."
Then there's the oti clause, explaining the cause of their disaffection: " ... they sailed off, pissed off that/because/by the fact that ..." The oti-clause will have an indicative verb, which we don't in fact hit until we reach "eia." Xenophon could have ended the sentence at apepleusan, and continued with a new sentence, e.g. efilotimhqhsan gar ... ("For they were pissed off ..."), but instead he strung the first sentence out longer by using the participle (filotimhqentes). It makes no difference to the oti-clause that follows.
The oti clause. If we took the oti away we'd have a simple sentence (simple in its basic syntax, that is):
(1) an accusative, tous stratiwtas ... tous ... apelqontas ws apiontas ... ou pros ton basilea (I'll unpack that in a moment, but for now it's enough to register that whole lot as a single extended accusative)
(2) eia, the main verb (of the oti-clause, if we keep that oti)
(3) Kuros, the subject (ditto)
(4) another accusative, ton Klearxon
(5) an infinitive, exein.
"(because) Cyrus allowed Klearchos to have/keep the soldiers .... That's to say: ton Klearxon is the direct object of eia, while the opening tous stratiwtas etc is the direct object of the closing exein! That may seem like pretty convoluted word order, but Xenophon is focussing on the soldiers (the soldiers that left X&P for Klearchos, that Cyrus let Klearchos keep), whose behavior led to X&P's sailing off.
(Keeping the word order, we could put into Cyrus' mouth "The soldiers that went over to you, I allow you to keep," "tous stratiwtas tous para se apelqontas ew s'exein."
So back to tous stratiwtas etc.:
"tous stratiwtas autwn "their soldiers"
tous para Klearxon apelqontas, "the ones that had gone off to K," "who had gone off to K." Participle with definite article. We need to distinguish this both from (i) simple participle, without article, and also from (ii) a relative clause. To illustrate:
(i) tous stratiwtas para Kl. apelqontas (no article with the participle) would mean "the soldiers, having gone off to Kl." That's not what Xenophon wants to say.
(ii) tous stratiwtas oi para Kl. aphlqon (oi relative pronoun, aphlqon aor indic) would mean "the soldiers, who had gone off to Kl." (that's to say, all of them had, note the comma in the English). That's not what Xenophon wants to say either.
tous stratiwtas TOUS para Kl. apelqontas means "the soldiers who had gone off to Klearchos" -- implying that not all of them had: he's talking only about those that HAD gone off to Klearchos instead of staying with Xenias and Pasion.
Tacked on to that is a participial phrase, ws apiontas eis thn Ellafa palin kai ou pros ton basilea. apiontas future pple, preceded by ws. This conveys the idea of their apparent intention in defecting to Klearchos. Lit. "as being about to go back to Greece and not against the King", better translated "with the intention [or at least the apparent intention, "ws" with the participle makes it less of a statement of fact] of going back to Greece instead of against the King." apiontas agrees with apelqontas agrees with tous stratiwtas (object of exein).
That's it, home dry. There's other points wthat could be gone into (the precise nuance of filotimhqentes, for instance, a very Greek and scarcely translatable notion), but that's the syntactical structure. Doesn't Greek makes great use of participles! (So much more flexible than Latin. But that's a different story.)
-- Incidentally, in your first sentence, Daivid, lol-illustrating a contract -aw verb in the imperfect, you've inverted "men" and "de." I'd make this "o men anqrwpos ... , o de lukos ...".
And I don't see the relevance of your final Lysias quote, which has no genitive of price or value, just the normal genitive after ek.
Hope you don't mind my shoving my oar in. I'm new here, and having fun.