I used to be terrible at spontaneously digging out quotes and phrases from films. Rather than figuring out what to say, I'd blurt out a (quasi-relevant) quote, even imitating the way it was delivered. This was kind of an automatic reation, rather than anything deliberate.
Works quite well, but can be a bit embarrassing if you have an odd taste in films (like I do)
I find now that if I know the other person well, there isn't much of a problem. But if I don't, I have to script. For example, if I go for coffee I will not only mentally rehearse how to get the coffee shop, but also what I'm going order and how I'm going to ask for it. If there are two of us and it is my turn to buy, I'll simplify what is being bought to avoid possible confusion at the counter (sometimes to the annoyance of the other person )
If I'm meeting a person I don't know, I always try to have someone else with me that I do know. Then they can maintain the conversation while I'm thinking. This isn't too bad, as most of my meetings with unknown people are about technology, which I can babble on about at high speed and without difficulty regardless of anything. It's mainly about dealing with conversation topics I'm not so familiar with, such as social small-talk.
The most frustrating thing is wanting to say something but failing because the conversation moves on before I have a chance (either I can't figure out how to say it or because I can't break in between other people talking).
I think most people, AS or NT do all of these things to some extent.