The “exif trick” and other measures in that article to sniff file contents are of little use in themselves. (OK, it's worth checking uploaded images are of the expected pixel size, but that's application-specific rather than a security problem.)
The article doesn't say what the threat model is that it's trying to address with filetype sniffing, but what this is commonly trying to do is prevent cross-site scripting attacks, where the attacker includes some active content in the file. Usually this is with HTML in files, which browsers (especially IE) sniff and decide to interpret as HTML even though that's not how the file is being served. Unfortunately, checking that a file begins with a PDF header, or represents a valid GIF image does not help you here because it's possible to make “chameleon” files that can be interpreted as different filetypes simultaneously.
This attack can be blocked in modern browsers by serving the files with a specific non-HTML Content-Type and an X-Content-Type: nosniff header. However there are more obscure attacks involving getting content into Flash or Java plugins that are not affected by this header, and it's not watertight against older browsers.
The really-safe way to stop XSS attacks on uploaded files is simply to serve them from a different hostname (ideally, a different domain name and IP address, but a simple subdomain is at least mostly-effective). Then you can let an attacker XSS the user-uploads-hosting site as much as they like without it having a negative effect on your main site.
Virus scanning is unlikely to prove useful for general-purpose file upload functions. If you are expecting people to use the site to exchange Windows executables then it can be worth scanning those for traditional malware, but for the general case you're typically concerned about attacks against the website itself—server exploitation, XSS, browser exploits—and those kind of attacks are not detected by AV scanners.
Your step (1) of creating a new random filename is a much better approach than “sanitising” user-supplied filenames as the linked article tries to do. Its “safe filename” function is not directly vulnerable to directory traversal, but it does still allow oddnesses like .. (on its own), the empty string, .htaccess, and filenames that would confuse a Windows server, like trailing dots, reserved names and over-long names.
You are right that secure file upload is much trickier than it initially seems, and unfortunately most tutorial code out there (especially for PHP) is pretty disastrous.
