In many languages, including French and English, verbs generally take zero to three nouns as "arguments".
- Zero: "it's raining"
- One: "I'm walking"
- Two: "I'm eating a cake"
- Three: "I'm giving you a cake" / "I'm giving a cake to you"
Traditionally, the first argument is called the "subject", the second is the "direct object", and the third is the "indirect object".
In English, when a verb takes three arguments, there are two standard ways to put the pieces together:
- Subj Verb Indirect Direct
- Subj Verb Direct to Indirect
But this doesn't change the roles of the nouns: if "I'm sending you a letter", or "I'm sending a letter to you", I am the subject, a letter is the direct object, and you are the indirect object.
That's why you use leur in your second sentence: it's the third argument to the verb. The first is nous (subject), the second is le choix (direct object), the third is leur (indirect object). Why do they go in this order? Historical reasons, really: that's just the way French and English evolved, and other languages can and do do it differently.
In the first sentence, on the other hand, the verb only takes two nouns as arguments. The first isn't stated (subject), the second is les (direct object). There's a third argument, but it isn't a noun, and only nouns fill in these three slots; other types of arguments, even if they're mandatory, don't fit into this same structure. (See also prepositional phrase arguments. These can also be mandatory: you can't just say *"I put the book", you have to put the book on something, or in something, or under something, etc. But they don't fit into the subject-direct object-indirect object system.)