Your understanding is correct. I would think of an Add-On as a configuration package that end users don't interact with. Add-Ons often define data characteristics to Splunk, such as the timestamp format, linebreaking configuration, and field extractions. Depending on what an Add-On contains, it might require installation on a UF, HF/Indexer, Search Head, or all of the above. An App, on the other hand, will typically only require installation on a Search Head because it only contains objects that an end user is likely to interact with, such as saved searches and views.
As you've noticed, you often need both the App and Add-On installed on your search head for the App to work properly. It's better this way, though; you wouldn't want to install a large, complex App on your indexers just to define a timestamp format for a sourcetype. Add-Ons are typically lightweight and harmless to install so I would go ahead and install them on the components that the documentation suggests. For your two examples:
App for Unix and Linux: http://docs.splunk.com/Documentation/UnixApp/5.2.4/User/DeploytheSplunkAppforUnixandLinuxinadistributedSplunkenvironment
Add-On for MySQL: http://docs.splunk.com/Documentation/AddOns/released/MySQL/Install
... View more