How to program Arduino manually via STK500?
Okay, by comparing the data packets my implementation sends with those from the avrdude log for the same sketch, I finally found the cause of trouble. I was sending the hex file byte-by-byte exactly as it is read from storage. But of course, the metadata needs to be skipped (i.e. the addresses at the beginning of each line, the magic bytes at the end of each line, and the newline). I added this simple fix, and now it works fine.
EDIT: Here is the preprocessing code from my Python3 script:
import codecs

program = b''
for line in open('sketch.hex', 'rb'):
    program += codecs.decode(line[9:-4], 'hex')