Sounds like you need to build a custom CKEditor plugin.
You could make it add a bunch of buttons to the toolbar (like the basicstyles plugin does for 'Bold', 'Italic' etc.). Or you can make it open a dialog with a multi-select [1] in it.
In both cases the UX is not ideal. If your plugin adds many buttons to the toolbar (and it sounds like it would) those will clutter the toolbar. OTOH a dialog won't be able to show your editors which classes have been applied in the current selection. The latter is done nicely by the 'combostyles' plugin since it automatically shows the active style in the select box.
I don't know whether CKEditor has the option to create a side-panel like Xinha had. But then again, such a side-panel is also not very pretty...
Another alternative is to make the 'Styles' dropdown bigger. That fixes at least the "select area is rather limited" issue. You can achieve this by including custom CSS [2] and adding the following rule in it:
.cke_combopanel {
height: 400px !important;
}
hope that helps,
Mathijs