In this Q&A, the answers assumed (correctly, as it turned out) that the player in question was using cheats.
I'm frequently seeing "[Player] moved wrongly!" and "Horse moved wrongly!" for all the players on my server, including myself, and I'm not using any cheats. What else could cause this?
Edit: The server is running in Linux on an i7-3770 and never using more than about 7% of its allocated 1 GB RAM. I'm not sure how to tell or configure how many cores it's allowed to use. I'm playing locally, so the network performance should not be an issue.