The problem isn't even setuid exactly but the size of the TCB. Setuid encourages a design in which tons of stuff that doesn't need to run as root runs as root anyway just because it's part of the same binary that needs elevated privileges. It's a footgun, but one can handle even a footgun safely if you practice trigger discipline and assume every gun is loaded.

Sudo (and other setuid programs) could in principle use privilege separation to punt everything not absolutely essential to an unprivileged context and thereby reduce the size of the TCB.