Directory trees are indeed another thing that are not enormously fast in Cygwin, but how often do you do recursive listings of directory trees? I don't even do that often on Linux because it's not fast there either.
Specific example: `find` has several tricks up its sleeve that it thinks are fast (e.g. looking at link counts on directories to test for leaf directories), but emulating the APIs that it uses for these tricks are part of what makes it slow on Cygwin (Cygwin will need to count the directories to emulate the link count, which makes it O(n^2) rather than O(n)). You can use -noleaf to turn this off. But `find` does other stats that make it slow.
I use a script that wraps `cmd /c dir /b /s /a` (IIRC) and cygpath for the few scripts I have that do much recursive processing, but it's very rarely a big factor. My biggest directories are on my NAS which is Linux.
My single biggest performance problem - as in, almost debilitating on Cygwin - are poorly written Emacs plugins that do filesystem access in the status line update callback (e.g., Projectile). But they're easily monkeypatched when they crop up.