My recovery partition was ~530MB and I tried the "Instructions on manually resizing the recovery partition." I think it's silly to suggest average users would need to follow those steps and hope they didn't mess something up. I was able to follow the steps but it reached a point where it simply said it couldn't shrink such partitions and I noticed other people were going deeper creating new partitions, assigning drive letters, copying contents etc. Just too much excess for me. Users can simply wait for a "fix" but I decided to see what I could do with other tools.
I opened "Computer Management" and then selected "Disk Management" and I shrunk the System drive by 250MB. Of course "Disk Management" won't allow you to extend the "Recovery" partition so I opened "Partition Wizard" which is a free utility (basic version). I opened it and then selected the "Recovery" partition and chose to "extend" it to the "250MB unallocated space", then click "Apply" and the changes were made near instantly. I then restarted my computer.
I then tried to install the "update KB5034441" again and whilst waiting I decided to open Task Manager, "Open Resource Meter" and noticed that "Dismhost...." was running and then "UpdateWinRE...." appeared and the update successfully installed. So increasing the size of the recovery partition worked fine for me.