Gymnopedie is in D, more or less, isn't it? I'd suggest looking for a piece in a complementary key like A or G, so that you don't have a jarring key change. G would be ideal if you are playing the first half of the Satie and ending on the D chord in measure 39. Finishing on D and starting on G gives you a V-I resolution so it will feel very natural.
I have an idea - how about the rondo from Clementi's Sonatina in G? Not so hard, not too long, moves briskly. I just tried playing bars 38 and 39 from the Satie and the first few bars of the rondo and they blend very nicely. It's public domain and the score should be easy to find. Technically it's Opus 36 number 2.
EDIT: here is the score. Look to start at "Allegro" at the top of page four. Dun dun dun Duh DA da dah, danadana dah...
You can pretty easily slice the Clementi down too. There is a natural end to the theme at the end of the second-to-last-line on page 4. The last line on page 4 starts a new section, and if you start thate you're pretty much committed to finishing the movement.
Another option I thought of would be to modulate to the dominant (A) after the Satie, then back to D to finish it. That's a common device. How many pieces are you supposed to be mashing together?