That's true, some of the songs we've heard in the character videos could definitely be parts of medleys. I guess we'll only really know when the official titles are confirmed. Personally, I wouldn't be surprised if the Luigi's Mansion, Triforce Heroes, Duck Hunt, Animal Crossing: Wild World, and Wii Fit U songs turn out to be medleys. I also think that Bonus Room Blitz is going to be a medley with Simian Segue, much like
this song from Brawl, but actually a proper arrangement this time.
As for new versions of previously-remixed themes, I'd like to see some that aren't the SMB Ground Theme, Jungle Level, Zelda Overworld, Green Greens, Mute City, etc. Brinstar Depths was a good choice, maybe they'll re-remix some other Melee tracks? New versions of Big Blue or Fourside would be great.
What other songs would you like to be remixed again, maybe in a different style than previous versions? I'd like to hear new takes on Gourmet Race, Pollyanna, Fever (Dr. Mario), and Obstacle Course (Yoshi's Island).
Oh, and we still need a new remix of the Brawl theme! I'm surprised that SSB4 didn't include an arrangement of Brawl's main theme similar to how Brawl had a remix of Melee's theme - hopefully we will see one in Ultimate.