Some rules that come to mind for me are:
* Apps must not alter data they did not create without explicit permission from the user.
* Apps must not cause advertising to be displayed outside of their own UI or when not in the foreground (the meaning of which depends on the platform's UI).
* Apps must not alter data on other devices without explicit permission from the user of the other device.
* Apps most not transmit data from the device without explicit user permission.
Some grey areas I don't know how best to handle are:
* Plugins and the like that might violate the rules despite the original app being ok.
* Agreements with third-parties (e.g. phone service providers). To what degree should it be up to the maintainer of the app store to enforce those agreements?
* Allowing installation of apps through other mechanisms.