Fetching information from the Internet about artist (or maybe even similar artists, eg. from last.fm) sounds interesting. I have no idea how to do this, but I'll do some research

You could have a look at amaroK's source, IIRC the needed functions for this features are written in ruby, so it shouldn't be too hard to understand the principles behind it.
So only playlist and progressbar would be visible? Or only a playlist? But there must be one free line for messages/user input (or at least the latter) anyway.
Well, for my needs, I don't need the "Playing: Honky Tonk - FunkyMonkey"-thingy, so I currently hide it by setting it's color to the terms-background. Same goes for the mode-line on top. Sure, there needs to be some kind of input-line, but the other things could be optional in my eyes.
I don't get it ;p Does it have to be in a few columns?
I'm open for suggestions, but the current navigation is not so "wicked", imho. It could also be two-pane(left/right) with i.e. a tree-view of Folders/Artists on the left and the songs on the right.
What in my eyes would also be awesome, is some kind of a "show-cover". Now, AFAIK there's no real way to show it in the term itself, but there could be a function to open the cover elsewhere, so i.e. press 'c' and the cover shows in feh or something like that.