Apparently ~75% of the positions in the lichess database (as of 6 years ago) have only been seen once ever. Average game length is 30-40 moves, so for the completely average player it would be like 10+ moves I suppose. The stronger the players the longer it will take: I found some comments suggesting 20+ for high level players.

I don't think the math is correct here. The 25% of positions that have been seen more than once represent more than 25% of the occurrences. Even if all of them would be seen only twice, you should already see them in 40% occurences.