Double quantum dot nanostructures embedded between two superconducting leads or in a superconducting ring have complex excitation spectra inside the gap which reveal the competition between different many-body phenomena. We study the corresponding two-impurity Anderson model using the non-perturbative numerical renormalization group (NRG) technique and identify the characteristic features in the spectral function in various parameter regimes. At half-filling, the system always has a singlet ground state. For large hybridization, we observe an inversion of excited inter-dot triplet and singlet states due to the level-repulsion between two sub-gap singlet states. The Shiba doublet states split in two cases: a) at non-zero superconducting phase difference and b) away from half-filling. The most complex structure of sub-gap states is found when one or both dots are in the valence fluctuation regime. Doublet splitting can lead to a parity-changing quantum phase transition to a doublet ground state in some circumstances. In such cases, we observe very different spectral weights for the transitions to singlet or triplet excited Shiba states: the triplet state is best visible on the valence-fluctuating dot, while the singlets are more pronounced on the half-filled dot.