How can I diff two Redhat Linux servers?

You're right, rsync is perfect for this. Use --itemize-changes (aka -i). Make sure you can run this as root on both sides (or some other user with full access to the machine):

rsync -ani --delete / root@remotehost:/

• -a is for archive, and basically makes rsync make an exact duplicate (apart from some cases involving links)
• -n is for dry-run, and means nothing will actually be changed (This one is IMPORTANT! :))
• -i is for itemize-changes, and outputs a simple-to-understand-once-you-get-it format showing every file that needs to be updated (the syntax is explained fully in the man page under the detailed help for that trigger).
• --delete makes rsync delete files that exist on the destination but not the source.

If you want to exclude certain paths, use commands like --exclude /var. The exclude patterns are relative to the source directory (which in this case is /, so they are effectively absolute).

You may want to investigate rsync's -c flag. From man rsync:

    -c, --checksum              skip based on checksum, not mod-time & size

I'd leave a comment to Alex Jurkiewicz's answer, but I don't have enough rep :'( yet...

One useful tool you should consider is rpm -Va. This will print out a list of all packaged files that differ from when they were packaged. This ignores any non-packaged files, but it's a very good way to get an idea of files that were changed since the install, that are part of the base system. They also include a flag that tells you if they are considered configuration files.

For example:

S.5....T  c /root/.bashrc
S.5....T  c /etc/yum/yum-updatesd.conf
.M......    /usr/bin/rdate
..5....T  c /etc/dbbackup.conf
S.5....T  c /etc/webalizer.conf
SM5....T  c /etc/sysconfig/iptables-config

So .bashrc and yum-updatesd.conf are "configuration" files that have changed in size, time, and MD5 checksum. rdate has had it's mode change...

The RPM database is a very useful thing.