>> I've tracked it down: it happens when multiple large images are
>> attached to the email (and displayed inline) and global-hl-line-mode
>> is turned on. The former slows down redisplay, the latter makes
>> redisplay do something with every cursor movement.
>
> I made a test message with 10 copies of a (black and white) 3k x 3k
> jpeg image, enabled global-hl-line-mode, but I don't notice any
> navigation problems. I wonder if there could be an interaction with some
> other package? Or do I need bigger / more images?

It's not consistent, apparently. I do have a message (with 2 images and multiple PDF attachments) where it looks like this:

       15095  97% - notmuch-show-command-hook
       15095  97%  - redisplay
          16   0%   - redisplay_internal (C function)
          16   0%    - eval
          16   0%       spaceline-ml-main

when global-hl-line-mode is on. Unfortunately, I cannot share this message. Generally, it only happens when one of the attached images is visible in the window.

If I stumble across this problem with a message that I can share, I'll post it here.