Speed of booting and speed of running programs may have different causes. The former may be slowed by system-level programs that load slowly - some antivirus programs are known to do this. AV can also slow program starts if it has to scan the EXE first - again, some are better than others.
You can test the first by running msconfig.exe and using a "selective boot" to temporarily disable all the startup items, seeing how fast it boots then. Then re-enable a few at a time until you find one that makes a big difference.
You can check for a slow AV by temporarily disabling your AV and running programs.
BTW, I recommend against using registry cleaners - my personal experience is that they do more harm than good.