Just some ideas for the Android app. First, the ability to change the order of playlists, and the songs in the playlist. Second, on the new ICS version the close application button has gone, which was useful for stopping it when wanted. Finally, official application for Android tablets, with more functionality like the desktop version.
Please just use 1 idea per topic, otherwise there's no chance to get them implemented.
Furthermore, most ideas have been suggested already: