Without knowing what apps are on your systems, I would hazard a guess: Yes, it will break a lot things. In general do not change permissions on objects in /usr/bin on the advice of a website somewhere. They are part of the system and the designers want them to be as they are. Not as an academic type at Stanford wants thewm to be in his little shop of horrors.
For example:
Everybody expects their scripts to be able to run ping. Because it uses a restricted TCP port number it requires setuid.
Disabling kerberos will break some networking apps.
As a counterexample
consider the at.deny, at.allow, cron.deny, cron.allow, /etc/sudoers files to control access to at, crontab, and sudo. Rather than changing permissions on system files.
There's some worryingly important things in there, like mount, ping, chage, crontab, and so forth. Just blindly removing the bits would probably be a disaster.
rather than remove suid. just chmod o-rx. I would have no issue with removing world execute on the following files. don't forget to review setgid binaries. They may also want to revise their STIG -- it's three years old! I also love the statement at the top of the page "Internal Distribution Only Not for Public Dissemination!" yet the damn page is available to the world. go figure.... *sigh*
Broadly I agree with frank_rizzo but you have yet again failed to state the Operating System or the intended purpose of the computer which you are "hardening".
If this server hosts say 10,000 user accounts you may find that hardening the permissions on the "passwd" command will keep you fully occupied with call tickets.
Your reference document is clearly for hardening the security of a RHEL database server in a student environment where hacking is a real danger.
General advice:
Do not change the SUID or SGID permissions on system commands.
However there is sometimes good reason to remove "other" execute permissions on certain commands because Linux "out of the box" will allow users to do things which are undesirable. Top of the list would be "mount". This assumes that you have allowed Shell access at all.