The first day of the LibreOffice HackFest in Munich is nearly over, and I am happy to say that I've already achieved what I wanted to hack on:
This is how the "Apply Style" combo box looks like from now on - in LibreOffice 4.0, we will show previews of the styles directly in there, helping the users to choose the right style conveniently.
I can imagine some follow-up work, like being able to edit the style directly from the menu entry, instead of having to choose "More...", and editing from there; if you are interested to hack on this, I'll be glad to show you where :-) - just mail me.