As I recall, it was rarely the case that a decision was actually connected to its result in any meaningful way, so it never felt like I was actually participating in constructing the narrative.
In one CYOA, in which you were abducted by aliens, you kept hearing that the aliens were actually searching for some sort of paradise, but you could never find it "by making a decision or by following directions". Instead, there were a couple of pages describing arriving at this paradise, in the middle of the book, disconnected from the linked pages.
My least favorite decision in a CYOA-style narrative, though, was in a sword-and-sorcery style narrative. You get a message of some kind written in a cipher. If you (the reader) choose to decipher it yourself, you get to read it and directions to the pages for the conclusion of the narrative. Otherwise, you read a description of a friend of the main character deciphering the message, and then telling you what to do, which leads to a different conclusion. As I recall, the conclusion which required doing the work of actually solving a puzzle was a "bad" ending, and the one in which you don't do the work was a "good" ending, which took all the fun out of having worked out how to decipher a Caesar cipher.