Is CCleaner legit? If not, recommendations?

MalwareBytes is usually my first run.

Malwarebytes

used to be, got bought out by another company. try bleach bit instead

CCleaner and RegCleaner used to be goto utilities, but sadly that's not really the case anymore.

If you're looking to clean up your registry, don't bother unless you've been running Windows for a very long time (years), in which case a clean reinstall is best. I'm serious - I know it's time consuming, but backup your "can't lose" files (like financial documents, resumes, etc) with an external drive, then do a clean reimage of the PC. Reinstall the applications you care about. It's worlds better than trying to rely on a cleaner software or an optimizer.