On my VPS, booting takes forever (long enough that for a long
time I thought the install had failed). I just rebooted again,
and it took over 7 minutes, see attached screenshot.

I would suggest skipping the seeding from /dev/hwrng by default
if /var/lib/random-seed is available. I’m assuming here that my
problem is not too rare — if it is, an option to disable the
seeding from /dev/hwrng seems like a good idea.