So turns out it's a bit more involved than what's been commonly told as a straight up 80% == bad scenario. ZFS by default divides[1] each vdev (RAIDZ or mirror set) into ~200 allocation regions called metaslabs[2].
When allocating from a metaslab[3] it will check if the free space in that metaslab is below the threshold defined by metaslab_df_free_pct. It seems the threshold was changed to 4% free space at some point[4].
If the free space is above the limit it will use the fast first-fit search, if not it will use the expensive best-fit search.
However, as noted that threshold is per metaslab. So if the pool is fragmented, even though the overall free space in the pool is above the 4% threshold, there might be metaslabs with less than that free, which will lead to the expensive best-fit search.
So it's not a hard limit, but it should start to be noticeable above 80%.
[1]: https://www.delphix.com/blog/delphix-engineering/openzfs-cod...
[2]: http://dtrace.org/blogs/ahl/2012/11/08/zfs-trivia-metaslabs/
[3]: https://github.com/openzfs/zfs/blob/master/module/zfs/metasl... (note metaslab_df_free_pct)
[4]: https://www.truenas.com/community/threads/zfs-tweak-for-firs...