Winterhazel (corylopsis). Here is one (corylopsis spicata) I've been working on developing into a clump style. Still got a ways to go (this year after blooming I cut back some of the longer trunks to encourage more branching) but produces huge numbers of very fragrant flowers in early spring. Probably works best as a large tree/clump due to the somewhat coarse growth, large leaves and flower clusters.
Cold hardy species as opposed to many of those already listed (gardenia, water jasmine, etc). This one spends the winter inside my general winter shelter where it is frozen for most of the winter.