Mmmm... So far, some interesting suggestions.
I've already listened to the Mendelssohn, the Dvorak and the Digimon Adventure song.
The Mendelssohn is a brilliant piece of music, but because it is so polyphonic, plus the fact that the piece already has a meaty Piano part - I somehow think it would be rather impossible to arrange it for piano solo simply because to physically play the melody without sacrificing any of the melodic notes, you'd probably need to arrange it for piano duet (or 2 pianos).
As for the digimon - the the accompaniment seems rather bland. I'm looking for something a little more challenging... Although I had to laugh, the intro to that song is in the Nico Nico Douga Medley that I posted.
I've listened to the Dvorak, and so far it's definitely got me intrigued. If anyone else has any good suggestions in the next day, then I'll hold off choosing until then... but so far the Dvorak is in front.
The shostakovitch isn't bad either - I just seem to be having a little trouble getting a full performance on YouTube, and there doesn't seem to be that many Variety Suite videos on YouTube. Any help?