I wonder if package installation tools could help here. Dropping to the commandline is always an 'advanced' option, but for the unwashed masses: what if 'dpkg-gui' shipped with a set of heuristics that classified packages based on their contents and displayed this to the user at install.
In the gnome-look example, this 'dpkg-gui' could scan the file listing and display a dialog saying that (based on the various rules) the 'Waterfall' package contains:
... with appropriate warnings about the items marked with a '!'.
The 'Maintainer scripts' type is (and always has been) a huge hole-in-the-waiting. You could scan each script looking for patterns ('/etc/', '/../') but the number of false positives (reading files versus writing) would be large - not to mention that any language could be used and the paths could be obfuscated easily.
One could argue that a user should know that a theme doesn't require these scripts, but that's really asking too much. People coming from Windows, rightly or wrongly, place some trust the installer because they can always "back out". This is not a completely unreasonable position. Given the innate "root-ness" of system packages, Linux may even be an even more vulnerable target.
Perhaps the 'Maintainer scripts' has a "Check..." option that creates a VM or a secure chroot/jail on top of a filesystem snapshot or overlay from which it can perform a delta analysis. It can then use this delta to amend the list of categories the package belongs to - perhaps highlighting new decisions in red, or disallowing them altogether.
This is an issue that will need to be addressed, and user education is not the answer. Like debugging clever code, this arms race has to be fought between the programmers themselves - not between the attackers and the "OMG Ponies" folks.