AVR: do I have to wait for the internal pullup to stabilize?
Yes, you need a delay for two reasons.
First of all, the internal pull-up is weak, so it can take a while before the voltage has risen enough to read as logic 1. How many clock cycles it takes depends on the stray capacitances.
Second reason is the input pin synchronizer, explained on datasheet page 70. The synchronization adds a delay, so even if you did toggle an output pin, you will need at least one NOP before you can read PIN register to see that the state has updated.
So most likely you need to add a delay loop which is the tightest code to achieve any arbitrary delay you want, due to weak pull up a few nops might not be enough.