Creating equitable, sustainable, and productive partnerships between computer science (CS) education researchers and practitioners is essential if we are to further improve CS educational outcomes, practice, and equity. Research-practice partnerships (RPPs) provide one promising approach for expanding how practice may inform research and research may inform practice. This early work, centered around a framework proposed by Henrick et al., and utilizing interview data from 11 participants, explores the ways in which six diverse RPP teams went about developing trusting and collaborative relationships as they worked together to solve local problems of practice. Barriers and challenges to collaboration and trust building, as well as mechanisms by which teams overcame those challenges, are discussed. The study revealed discrete team behaviors, norms, and structures that may contribute to building more collaborative, trusting, and sustainable RPP relationships. Limitations are presented and implications for current and future RPP teams, as well as possible future research directions, are addressed.