Sendmail can safely be made setuid to root. At the point where it is about to exec(2) a mailer, it checks to see if the userid is zero; if so, it resets the userid and groupid to a default (set by the u and g options). (This can be overridden by setting the S flag to the mailer for mailers that are trusted and must be called as root.) However, this will cause mail processing to be accounted (using sa(8)) to root rather than to the user sending the mail.
If you don't make sendmail setuid to root, it will still run but you lose a lot of functionality and a lot of privacy, since you'll have to make the queue directory world readable. You could also make sendmail setuid to some pseudo-user (e.g., create a user called sendmail and make sendmail setuid to that) which will fix the privacy problems but not the functionality issues. Also, this isn't a guarantee of security: for example, root occasionally sends mail, and the daemon often runs as root.