I think, given my perspective, this is the right section where to ask such a question:
What do you expect from a CYOA?
Do you choose routes to a) find the best possibile solution or b) just go RPG and try what suits you to see how the PC will survive the story?
I’m deeply interested in this.
Works set their own expectations, I think. The way I play CYOA depends a lot on how those expectations are set, and how they’re met. Does it seem as though you can play according to some kind of consistent strategy? How is that strategy interesting? What sorts of things does the author want to give me control over? (Also, sadly, ‘does the author understand CYOA at all, or are they just linking straight prose together with arbitrary choices?’ is a big one.)
One of the big things that a lot of old-school choice-based games have, for instance, is Moral Pointers. This shows up a lot in children’s CYOA, the authors of which love to go on about You Are Responsible Because You Decide. (Then I usually pick the obviously unfavoured options, like abandoning your friends in favour of a cute boy, or kissing a cute boy on the first date, just to see what a strange twisted worldview the author’s moral system is going to produce.)
Then there are CYOAs that are more explicitly about the author fucking with the player: giving them choices that are traps, or offering choices only so that they can be denied. If I figure out that I’m in one of those, I generally disengage, stop caring about choices, and either lawnmower or pick randomly.
Awesomeness. Same as with anything. 
If the Writing Just Sucks: I flip through for the funniest pictures, and read the text near those.
If the Writing is Tolerable: If there’s a specific goal provided, I usually try to pursue that goal on the first play-through, and explore alternates on revisits. If the PC is strongly characterized and I like the PC, I try to be mostly-true to the PC but lean gently toward optimal choices … if the PC is strongly characterized and I dislike the PC, I try to screw them over for kicks. If the PC is left vague or cypher-ish, I lean toward whichever choices are likely to be funny or strange.
If the Writing Rocks: Pure RP approach. Livin’ it.
The writing is my main cue for how much I trust the design, basically.
With the ones I’ve read this last year from Choice of Games and Varytale I almost always go an RP route and try to play with a consistent goal or perspective. Like playing the zombie games without killing anyone, being as militant as possible as a boxing coach etc… Hell, this is how I play all games that offer choices on how to play. I played through Skyrim and Tactics Ogre as a pacifist, pokemon only using grass-type, and Dwarf Fortress without mining.
Not to mention, I’m sure, Deux Ex (first one) as a pacifist.
Funny, though, I get the impression most everyone decides to go the Pacifist route in DE1, if for no other reason then because it’s so much more interesting. My point being, does the choice mean anything if most people will choose the same route and the game is simply more fun to play a certain way?
My impression could be wrong, of course, thus flawing my whole reasoning. But at this time of night, and after 48h without sleep save for a non-sleeping two-hour shuteye, I’m sure I could be spouting worse gibberish.
I had quite the complex experience with the first Deus Ex. I completed the first mission without really caring about who I killed, and when I used explosives to get past the last guards I was actually shocked by what a horrendous mess I’d made of them. When my brother in game upbraided me about it, I genuinely felt bad and I vowed not to kill anyone at all for the rest of the game, and so I didn’t until about half-way through when the stakes were raised and I was fully absorbed into fighting the people I had once worked with, and as a true believer I killed one of my old co-workers while trying to evade capture, and in return the other co-worker (was his name Gunther?) hunted me in revenge.
Nowadays with achievements you’re not rewarded as much for playing organically, but rather encouraged to either stick purely to one path or other, or else encouraged to do everything no matter how little sense it makes for your character.
But uh, on topic, I guess the ideal CYOA would play a bit like my experience with the first Deus Ex: you’d read through choosing choices you find meaningful for the character and experiencing the fallout from these choices.
Your experience with Deus Ex seems much more organic than mine was. I simply did not want to kill anyone because they were paid underlings, really, if it was possible for me not to kill them so much the better. Also emotionally involved, but in a different way. 
Naturally, I had no such compulsions about the cyborgy-things that came later.