Helleborus are superb plants and have come a long way the past few years with many new cultivars and more up facing blooms. Not all of them blooms in the winter as some will wait for spring, but many will in a climate such as yours and they can have very ornamental variegated foliage as well.
Winter-flowering pansies. Lots of color.
Skimmia japonica has very nice buds over the winter, needs acid soil.
Some snowdrops can start to bloom very early and so can Cyclamen coum.
Hamamelis is an ornamental bush that blooms in the winter.