First of all let's clear up some misconceptions. Modern hard drives cannot be low-level formatted by end users any more1 2 3 4, despite what various programs might claim. Drives nowadays are low-level formatted at the factory using a servowriter, and all you as an end user can do is zero fill them.
What Windows allows you to do is a full vs. quick format. The latter simply deletes the File Table and other file system structures so that to the OS the drive/partition looks to be empty, but the actual data still exists on disk and can be retrieved relatively easily. The former zero fills the drive (in Vista+ only, full format in XP and earlier did not zero fill), checks the drive for bad sectors and and finally recreates all the necessary file system structures.
Which one should you select? Well that's up to you, but since modern drives are huge and a full format takes ages, if you're sure the drive is defect-free then a quick format is all that is required before an OS reinstall.
Finally, the difference between only reinstalling the OS vs formatting and then reinstalling. If you do the former then it's not as if the files from the old and new installations will get mixed up (which obviously has the potential to cause problems). Instead Windows will move all the old installation's files to a Windows.old folder, that you can subsequently get rid of using Disk Cleanup. So in terms of starting afresh there's no real difference between the two, except that the former will allow you to access any files from the previous installation if required. Personally however I ensure that I have backed up all my important data, after which I prefer to quick format and reinstall. A completely empty partition to begin with results in the least problems as well as a quicker install since no time is wasted moving old files.