Horses glitch out and warning is logged in console when climbing up stairs

When climbing up blocks while riding a horse, the horse occasionally glitches slightly (it gets reset backwards by the server), and the "Horse moved wrongly!" warning is logged in the server console (or game log in singleplayer).

In particular, this happens almost always when walking up stairs with horses, although it doesn't appear to happen with slabs. However, this issue has also been reported to occasionally happen if there are no stairs involved (e.g. MC-147523).

Steps to Reproduce

1. Summon a moderately fast horse, e.g. by using the command provided below.

   /summon minecraft:horse ~ ~ ~ {attributes:[{id:"minecraft:generic.movement_speed",base:0.35d}],Tame:1b,SaddleItem:{count:1,id:"minecraft:saddle"}}
   

2. Mount the horse and climb up stairs with it.
3. As you do this, pay close attention to the horse's movement and frequently check the server console / game log.

Expected behaviour

The horse can properly walk up the stairs.

Actual behaviour

The horse is very slow walking up the stairs; additionally in the server console / game log, warnings of the following format are sent:

Horse (vehicle of <user>) moved wrongly! 0.5

Notes

This is a new problem since the 1.9 update, and it happens with all horses, no matter their speed.

This also affects other entities than horses, however it appears most frequently with horses in regular gameplay. For example, camels with Speed II are also affected by this when sprinting, and so are pigs with Speed V.