Here are some shrubs that I have experience of in similar situations:
Prunus lusitanica - dark green laurel like leaf, white plumes of flowers (in May) grows quickly and makes good background. Can prune hard to required height.
Mahonia japonica - holly like leaf, scented yellow flowers winter, followed by matt purple berries. Good in shade. Or Mahonia x media 'Charity'. can't really prune but doesn't need it much.
Aucuba japonica 'Crotonifolia' - spotted laurel, get male and female plants for large red berries from Feb onwards. Good in shade. Can prune hard to required height.
Cornus alba 'Sibirica' - red stemmed dogwood, and/or Cornus sanguinea 'Winter Beauty' orange/yellow stemmed dogwood.
Osmanthus x burkwoodii - Oval green leaf, small flower heavily scented.
Lonicera fragrantissima - needs full sun, evergreen in the south, fragrant white flowers Jan/Feb
X Fatshedera lizei - wall shrub (need support) good in shade.
Eucalyptus gunnii - grey/blue leaf, can pollard regularly to maintain desired height.
Remember, you can grow different ivy and clematis up trellis or plainer shrubs.
