You're right, find won't call stat() unless it needs to. It doesn't need to for recursing through the directory tree because readdir() returns dirent.d_type these days to determine if a name is a directory.
Yes, those stat() calls can be very slow in aggregate on a large tree, especially from HDD (due to seeking) or network filesystem, if the stat information isn't already in cache.
du -a will need to do a stat to get the file size, which is comparatively expensive; I don't think find will (not sure)?