I was seeing this issue on a fresh stretch install, on a amd64 EFI system with non-free nvidia driver.
I installed plymouth, plymouth-label, plymouth-themes, libplymouth4 0.9.3-3, as well as fontconfig-config, libfontconfig1 2.13.0-5 from buster to satisfy deps. This did indeed fix the issue for me. Note that I also had to upgrade fontconfig from 2.11.0-6.7+b1 to 2.13.0-5 as the plymouth update-initramfs hook was bailing running fc-cache. I believe this is caused by an issue with the -y flag in the fc-cache present in stretch. Might be worth adding a version to the plymouth-themes->fontconfig dep, although this will probably only occur for mixed stretch/buster users.
