I'm not a teacher, but I think a simple change to "objects in motion stay in motion" could help with teaching it. Instead, tell students that any change in motion always has a cause, then ask them for the cause in different scenarios. Why does the ball stop rolling across the room? Why does the rocket launch into space? Why does the falling feather stop as it hits the ground? Then, ask what happens if there is no cause for change. Now you are left with the original law. That object will stay in motion.

The issue is their intuition for the general case is actually gathered from a special case.

You need examples that point at the general case - like Newton's cradle.

Conservation of momentum helps.