As for the problem of trusting Cally, I think that that arises from Avon seeing her as being akin to Blake: ready to fight, die, and sacrifice others as necessary in pursuit of the greater good. If Avon could be convinced that his own well-being has become of prime importance to her.... How, I leave as a exercise for the writer. One possible angle: Cally chooses some action that harms the rebellion simply to save Avon.
Interesting and likeable.
Another: somehow Avon's life becomes crucially important to the success of the rebellion, perhaps he has to do some computer magicking on an on-going basis to allow other things to happen undisturbed by the Feds.
This would give the writer a chance to make him the initiator of the relationship, if they wanted to go that way, whereas in most other writing situations I would see him waiting to see how *she* feels. If he was doing some vital, *well-guarded* steady job, he would be more inclined to take an emotional risk than when they are running around nearly getting blown up each week.
Another possibility, of course, is a telepathic link being created. He would have the assurance of being able to communicate with her in near-absolute privacy, she would have the telepathic companion she needs, leaving her less vulnerable to outside influences, and one tends to assume lies would be a bit more obvious mind-to-mind (although Cally's tricking of the Thaarn would be evidence against it)-- still, it might make Avon more inclined to trust fully. The other nice thing about a telepathic link is it would allow the author to indulge in a bit less restraint in the dialogue; the mind may be harder to censor than the mouth.