P.S. Oh, and the "Next in queue" info would be also cool, that's also there in ST2.
An idea about keeping playback history: instead of removing songs from the queue, after they have been played, how about moving them to the end of the list instead, or just use a coloured background to mark them played (just like in ST2).
An organising/sorting idea: in all windows where songs are listed, you could add different columns for Artist, Key (very important imo), Year, Genre, Last Played, Play Count and then, when tapping on a column header, the list would instantly be ordered by that column. Tap once, it is order A-Z, tap once again, it is ordered Z-A.