To me what you have realized is a shortcoming of the Categories concept. What you're asking for is that one should be able to arrange categories in groups: this is perfectly reasonable, and already happens with links (the Links widget can have subsections, as you already know). So I think you should definitely suggest that to staff in the Ideas section of the forum: we should have category groups the way we have link groups (now unfortunately called "link categories", which confuses things).
The way things are now, I can think of the following:
A. Retain the "artists" categories only, and use either a text widget or pages for the other list of links. Shortcoming: you'll have to update this list manually each time you add a relevant post. But it can be easier than it sounds (if you use pages, you can drag-and-drop post titles).
B. A tricky way would be retaining all categories the way you have them, create pages whose names link to the category pages, and use the Pages widget - completely removing the Categories widget. No manual updating this way. Shortcoming: you'll need one page for each category, so with all those categories this needs a lot of work in the beginning - I don't think it's worth it.
C. Just take advantage of the parent and child possibility. Two parent categories, all the rest subcategories to the one or the other. The only problem is that the two parents cannot be titles only, they have to be actual categories: so you'll simply have to assign each post to the parent category as well.