What has CCleaner to do with running the removal utilities for other security tools?

Recommending CCleaner as a general procedure is not a good idea. It doesn’t replace the respective removal utility (like the ones listed at http://thewebatom.net/uninstallers/security-software/) and, moreover, in some cases it can cause more damage than good. By recommending CCleaner together with removing remnants of security tools you are giving the wrong impression. The goal is not necessarily related to the tool (to say the least).

I don't see any need to "re-download" as the installation file remains the same.

When “everything” is working correctly, there is no need to re-download. Avast files are not published (officially) with checksums. The setup.exe could be corrupted (either by filesystem problems, bad download, wrong download source, malware,…).

I don’t think that any forum user that is trying to help needs to cover each and every possible situation and question the OP with so many possible options. By re-downloading from the official site a clean installer, the OP might be solving many of those potential situations.

And besides it is always better to download before removing any anti-virus. The reason for this is that there is very little delay in getting avast up and running. :)

I don’t know about “delay”. Generally speaking, the recommendation is to download all the needed tools to repair (as the new setup.exe and the removal utility) and then start with the procedure (if we are NOT talking about malware situations). But in this particular case, I don’t understand why you need to mention this now and here. The OP was asking about the installation procedure (Windows Safe or Normal mode for installing Avast), not the download order.