Well, I thought I'd post a followup saying that it worked out pretty well.
After finishing the Ubuntu 13.04 installation, it didn't boot linux -- just booted Windows 8 as expected.
I had followed all the instructions and moved EFI/Microsoft/bootmgfw.efi away and at that point, it booted linux, but I couldn't get it to run rEFInd. I didn't worry about getting rid of EFI/redhat/grub.efi because I wasn't using redhat nor did I have an EFI/redhat directory.
However, after a lot of flailing, I discovered that it first tried to boot EFI/Microsoft/bootmgfw.efi, then it tried to boot EFI/ubuntu/<something> where something was either grubx64.efi or shimx64.efi. I'm not sure which because I discovered this by moving EFI/ubuntu to EFI/ubuntu.old and then it started booting rEFInd. I guess that luchnkov's Redhat installation added the redhat path to the list while my Ubuntu installation added the ubuntu path to the list.
This last part is curious, because I had trouble using efibootmgr to modify the path. I found that most of the time when I ran efibootmgr -c ..., it did nothing. Then I found there was an error in the dmesg log output saying:
efivars: set_variable() failed: status=8000000000000009
for each time I ran efibootmgr -c. This is likely related to this bug:
https://bugs.launchpad.net/ubuntu/+s...x/+bug/1167622
which will presumably be fixed soon, but not yet.
In any case, after moving the EFI/ubuntu directory out of the way, rEFInd would start and I could choose between booting Ubuntu and Win8.
BTW, I turned Secure Boot off in the BIOS to make things easier.
Thanks for everyone's experience in this thread.
--Jim--