To be precise: there is no real difference, as both are insecure. There are viruses which infect the MBR, which is an area not touched by formatting, be it quick or full. While Windows 95 basically killed off this type of viruses by doing some simple checks for them, running in protected mode and, generally speaking, preventing programs from writing directly to disk, they have made a comeback. Some time ago there was a run of a rootkit that infected the MBR under Windows. If you've got that then you have to boot into a clean environment, ie start from a live-CD or attach the harddrive to another computer, and clean the MBR before formatting the partitions. Overwriting the drive (whole drive, not individual partitions) is another way to accomplice the same.
PS! "Full format" nowadays means "check the disk for inconcistencies", not "clean it completelly". It in no way prevents anyone from recovering the files, it simply makes sure that all areas on the drive are readable. It's simply how drives now work.