Well, after a bit of frustration, I finally got the courier-imap package installed on RHEL and I had the IMAP server running, but I wasn’t able to successfully authenticate with it. Eventually, I realized that I had forgotten to start the courier authdaemon:
sudo /etc/init.d/courier-authlib start
Bam. Then things started working. Duh.
I also had to do two small tweaks to my .fetchmailrc – basically formail and procmail are now in /usr/bin instead of /usr/local/bin.