My first guess on the Salvia would be Pineapple Sage (Salvia elegans.) If you can rub the leaves they should have a fruity smell. There are several varieties of Salvia elegans that have slightly different habits and fragrances, like 'Honeydew Melon' and 'Tangerine', but the 'Pineapple' is the most common.
You are right, that is a great combo! I just love the blue-gray and red together. I'll have to see about making a similar combination here.