Just have collapse-able categories. If you're listing by artist, just have the artists shown until you expand their list, if you're listing by song title, just have the alphabet shown until you expand, etc.
Oh, and DEFINITELY allow for custom lists, not just playlists, but a custom selection to appear 'above the fold', so to speak (so a 'party mix' can be set up, or a 'favorites').
As for showing stars? Simple, have them ghosted behind the score...for bass, just have it fade back and forth between the two scores (and be able to list by bass stars as well).
However, since we can already sort by stars, this is a very minor concern (except for bass) assuming that all current scores will accurately carry over.