In California, your choices should be drought tolerant, and (in most areas) tolerant of more alkaline soils.

Irises work very well here, and they can provide a touch of blue that the rose garden may otherwise lack.
More and more of them repeat, too.
Modern thinking discourages the cutting back of iris leaves,
so even when they're not in bloom, you have that strappy blue-green foliage, which is a great addition.

Brugmansia work well in most California gardens.
Where the climate is mild (as yours appears to be)they're year-round bloomers.

Most salvias are great additions to California gardens. Plant them here, rather than acid-loving lavenders.

In shaded areas, where roses won't grow, we've done well with fuchsias.
CAUTION: Care in selection required here!
You want to look for mite-resistant cultivars, unless you want to spray all the time. (We don't.)

Where temperatures are mild enough, we've found a few Plumerias are terrific in the rose garden.
They add an entirely different sort of visual element, and they come in a wonderful range of colors.

Jeri

I have Iris, Daylily, Geranium 'Rozanne', Shasta Daisy, Boxwood for structure (short hedges, clipped globes etc), Santolina, Lavender, Rosemary, Saliva.

Some salvias spread like crazy so be careful with them--but they do attract Hummingbirds. Pineapple Salvia and 'Black and Blue' have spread pretty aggresively into my roses and I must dig them out. New salvia 'Mystic Spires' appears to be really good. I have one planted at the base of Ambridge Rose and it looks great. Doesn't look like it will be a spreader.

Small no-to-low care shrubs are good especially that period when the roses are cut back: Common Myrtle clipped into shapes, Pittosporum 'Golf Ball', Calocephalus brownii, Coleonema pulchellum 'Sunset Gold', Lonicera nitida 'Lemon Beauty', ornamental grasses that don't reseed agressively like Blue Oat Grass, Festuca Glauca, Carex 'Toffee Twist'.

Can't say enough good things about Geranium 'Rozanne' ('Jolly Bee' is very similar). Just tall enough to cover the bare base of HTs, blooms like crazy, doesn't reseed, cool lavender-blue flower color really complements any rose.

Here is a link that might be useful: Coleonema 'Sunset Gold'

My best is Salvia 'Coral Nymph'. It fills in with lovely airy pink coral color at the front of the border. The finches and hummingbirds are all over it. I plant one 6 pack a season in a 20 ft. border and it reseeds a bit. It did not survive our frost but it's worth re-planting.

Here is a link that might be useful: Salvia 'Coral Nymph'

I have planted stella d'oro daylillies, walker's low catmint, sunny border blue veronica, lavender, and purple homestead verbena among my roses. I'm not overly thrilled with any of these yet, but I'm going to give them each another year or two to fully establish and show their stuff.

I'm going to try some other perennials next year in other rose beds, so I'll be keeping an eye on this thread for suggestions. Thanks for starting the discussion.

Hope

The best thing I ever planted with my roses has been society garlic. I have not had the plagues of aphids I had since I planted this all throughout the rose beds. I get a few in early spring when the roses first leaf out, but it's nothing serious. I don't have to spray anymore for aphids and I think it allows the lacewing and ladybug populations to build up.

I like to have iris with my roses. The earthworms really like thoes iris roots! On the climbers, I have some clematis. The spring blooming pelargoniums do well with the hybrid teas. They fill in at the base, but don't get too tall. You can cut them back easily any time. Stock is another good choice for winter and smells great in the evening. With the shorter roses, I like to plant pansies and violas .

One of the prettiest combinations I ever did was strawberries and alyssum at the base of Double Delight. I remember a fantastic planting of portulaca at the base of a row of Chicago Peace roses at the fairgrounds years ago.

In Northern California, I have these perennials mixed in with my roses, penstemone, salvia, scabiosa, yarrow, blanket flowers burgundy, oranges & lemons, perennial geraniums Rozanne, Jolly Bee, and Brookside, verbascum, sidalcea party girl, sun loving foxgloves like excelsior and camelot, English lavender, sea lavender, veronica, creeping lobelia, Japanese iris, Chinese foxglove, and lots of campanula. With the salvia and penstemone you have to be careful to select smaller varieties. Many of the hardy geranium do not like full sun, I have found that Jolly Bee handles the sun better than most. My favorite scabiosa is giant blue, the flowers are Hugh and the butterflies love them. I am somewhat limited since I have such intense full sun, and limited space. I miss my bearded iris, I only have a few due to limited space.
Diana

I am in the process of re doing my rose bed this fall with it being completed in the spring. However, we planted Salvia 'Mystic Spires' by one of the KnockOuts at the beginning of this summer and that is really pretty. If the Mystic Spires does not overwinter I think I will start just growing it an annual every year. Love that plant.

Kate

Daylilies, lavender, salvias, hardy geraniums, bulbs, azaleas

Carla

For Heaven's Sake, before you plant Society Garlic, find some of it and smell it!
It may repel some aphids, but it also repels ME. And some people are violently allergic to it.
It was planted in a small public garden near here, and they almost lost all the volunteers.

Jeri

I don't have much room for too many other companions as I have so many daylilies mixed with my roses, but wallflower, alyssum, veronica, and society garlic (I can't smell worth a darn anymore) are nice.
Kathy

I also have foxgoves, pentas, scented geranium (citronella), achillea, coneflowers and chinese garlic (no stink and flowers white this time of the summer). Chives and nemesia are other short, good fillers along with thyme, pentas, bacopa and heliotrope.

Lots of different salvias,

Wow, Karen, what a colorful and attractive garden! Looks great! I'm not planning on so much variety- roses and peonies, and then some easy care herbs and perennials- I love catmint for one, it makes such a nice mat, about 3 ft across and the bees like it. I definitely want some small evergreens. I hope to make space to tuck a couple small benches in and really enjoy my garden. Brandy

Thanks Brandy. Your choices sound wonderful. Small evergreens give your garden a finished look, even when the roses and peonies aren't in bloom. Like you, I also love catmint. You'll have to post some pictures when you're done.