The guide says to install python-selinux last, except this doesn't allow python, thus emerge, to understand selinux and proper selinux permissions will not be applied. I suggest installing python-selinux immediately after the coreutils. Reproducible: Always
Please post your emerge --info.
It doesn't matter. The filesystem is labeled after this point, so the correct labels don't need to be set at this point.