I've changed the name of this from 'Release Criteria' to 'Release Branch Criteria' - as I really think they are one and the same. I think that it is vital that we guard master and release branches to ensure that other developers and users do not find them broken. I think that we must proactively prove that changes aren't harmful. I think that the below is what we as a project should demand at all times from our master/release branches. Code that breaks any of the below should never hit master/release branch.
Think of each step in this process as part of a pipeline - with the end being a 'releasable'; but not necessarily released candidate.
Each phase gets slightly more complex, and consumes slightly more time. These definitions are fluid, and will change over time.
Packaging for debs/rpms works.
Installation of packages works
API is tested for consistency with preceding versions to confirm consistency.