1. Do a nandroid backup of your current ROM if you want to restore it later.
2. Download the current version of the RUU for your phone in exe or zip format from this page.
3. Run the exe version of the RUU in Windows or the zip version as a PG86IMG.zip file through the bootloader. If using the bootloader method make sure the file is named exactly "PG86IMG.zip" and placed in the root of your SD card before starting the bootloader.
There is no need to unlock the bootloader before running it if you are S-OFF and there is troubleshooting information in this post if you have problems. It may be necessary to run the RUU twice if you have a custom bootloader installed when it is run the first time. If the utility hangs after flashing the bootloader from Windows just cancel it and restart.
I recommend downloading and installing the OTA(s) immediately after flashing the RUU to get the most current firmware while still 100% stock, but the OTA firmware update(s) can be downloaded as a separate PG86IMG.zip file if you forget or can't do that for some reason.
4. Flash a custom hboot using the instructions in this post. My recommendation for a good general purpose hboot is the JBear GB 1.50.5050 version unless you are running an ICS Sense ROM like stock or Cool ICS that requires an ICS bootloader (1.57.xxxx or 1.58.xxxx).
5. Connect your phone to a PC and start the bootloader in "fastboot USB " mode, then issue the following command to flash your favorite recovery:
fastboot flash recovery recovery.img (where "recovery.img" is the name of the recovery file in your ADB/fastboot directory)
6. Boot into recovery and restore a nandroid or flash another custom ROM. You may have to wipe cache+dalvik and restart recovery if you get any error messages from the recovery program.
That's it. You're now updated or re-synced with the current firmware, the hboot that meets your requirements and your favorite recovery.
Here are some additional links that might be helpful:
4EXT Recovery OP for the Evo 3D CDMA thread with a direct link to recovery.img in the download section (not the most current version)
Current TeamWin (TWRP2) touch recovery for the CDMA Evo 3d.
Virgin Mobile OTA firmware only in PG86IMG.zip format.
Sprint OTA firmware only in PG86IMG.zip format.