With the disclaimer that the majority of my paragraphs are shorter rather than longer I will say that I start a new paragraph when:
- A different character starts speaking. (This should be obvious but is an oddly common mistake in newer writers.)
- A different character begins a new action.
- To bring emphasis to a certain action.
- Because it feels right.
And here's an example out of my current WIP.
Dropping his bag to the ground, Lowen settled on heels and dug his fingers into the slick muck. He paused for a moment, stomach already protesting what must come next, took a shallow breath and ate it.
As he expected, it was terrible.
There was very little earth left in the mud and he gagged, wondered if there was enough to work properly, and forced himself to swallow it. He coughed, gritted his teeth to keep the stuff down. His soul reached out to the earth.
This demonstrates the latter two points rather than the first two. (The first two should be fairly self-explanatory.) Some would probably put all of the above in a single paragraph. I broke it up because I wanted attention on the line
As he expected... and I broke the third paragraph off separately because (in my mind) it seemed a different thought and felt better that way.