I believe the conventional rule is that you start a new paragraph when the speaker changes, not when any quote starts. You may have other text before the quote, as long as it's not a quote from a different speaker. You may or may not start a new paragraph when a quote follows non-quote text. Indeed we routinely precede quotes with text identifying the speaker, like "John replied" or "Mary paused for a moment before speaking."
So by the conventional rules:
Simon stared at her. "Are you serious?"
"I certainly am," Mary replied.
Do not normally run multiple speakers into one paragraph:
Simon stared at her. "Are you serious?" "I certainly am," Mary replied.
This rule can be counterproductive when you have two or more short quotes within a block of narrative. I sometimes ignore it in such cases, but I'm sure an English teacher would mark it wrong. Like:
We had a long discussion about which way to go. John said, "Let's head north." But others in the group where not sure this was a good idea. We argued for a long time. Finally Alice said, "Okay, let's go north."
I'd prefer to write it like I did above, one long paragraph, but purists would say that "Finally" should begin a new paragraph.