Structures and binding energies for bimetallic clusters consisting of a large variety of atomic species are obtained for all atomic sizes N<=40 and all concentrations, using an interatomic potential derived within a quasi-classical description. We find that increasing the difference between the two types of atoms leads to a gradual disappearance of the well-known homo-atomic geometric magic numbers and the appearance of magic pairs corresponding to the number of atoms of each atomic species in binary nanostructures with higher stability. This change is accompanied by structural transitions and ground-state <--> isomer inversions, induced by changes in composition or concentration. We find a clear tendency towards phase separation, the core-shell radial segregation being predominant (energetically favored) in this model.