I've made this answer community wiki, so if you have over 100 reputation please feel free to edit in any further suggestions
sfc (System file checker)
Checks system files (DLLs, etc) and will replace any that have been unexpectedly modified (or corrupted, etc) with thier original versions (from the DLL cache, if available, otherwise the user must provide a copy via install media, etc). On Windows Vista and 7 it also protects some system folders and registry keys.
chkdsk (Check disk)
Scans a hard drive partition looking for errors and will repair any that it can. Primarily it will fix various errors in the filesystem (with the /f "fix" parameter), and can be used to detect (and try to recover data from) bad sectors as well (with /r).
bootrec (Vista and Win7)
(Note: I think these may only be available from the recovery console)
fixmbr and fixboot write a new master boot record to a disk or new volume boot record to a volume, respectively.
bootrec needs a command line argument to select the desired action, which should be one of:
/fixmbr - writes a Windows 7 or Windows Vista-compatible MBR to the system partition.
/FixBoot - Writes a new boot sector to the system partition by using a boot sector that is compatible with Windows Vista or Windows 7.
/ScanOs - Scans all disks for installations that are compatible with Windows Vista or Windows 7.
/RebuildBcd - scans all disks for installations that are compatible with Windows Vista or Windows and lets you select the installations that you want to add to the BCD (the Windows bootloader).
** Warning ** Fixmbr will overwrite the current entire MBR, if you have a Dell, HP, Sony etc, you may have a custom Master Boot Record, if you run the fixmbr on these PC's it will break the functionality of some bios tools such as hardware diagnostics and Factory Recovery partitions. They are very difficult or near impossible to restore these custom MBR's once they are overwritten. FixBoot on some OEM PC's can also break some of these bios hotkey functions, because it only overwrites the Partition Boot Record of the logged on partition. I always suggest to make a backup of these custom boot records on new systems in case of problems.
dism (Deployment Image Servicing and Management Tool, Windows 7)
After installing Win7 SP1 you can use dism to free diskspace by removing the SP uninstall files:
dism /online /cleanup-image /spsuperseded