Depends on whether yours is male/female, neutered or not. Cavs are usually very amiable with other dogs, but two females might not get on, likewise two entire males. If you have a neutered male, then get a spayed female and vice versa. Most rescues would be neutered anyway, and most rescue homes would not rehome with an entire/unspayed dog. As for your other issue, no I don't think its ever too late, even for an older dog a younger one often gives it a new lease of life. Also any rescue would expect the dogs to be introduced before rehoming, and you could take one on trial to see. Find a rescue dog and start taking it for a walk with yours to get them introduced on neutral territory. Always assuming that yours has shown no aggression to other dogs it has met!