Newcomers:
Shulk, Pac-Man
Veterans:
Wario, Meta Knight
Palutena is basically already revealed.. It makes sense for her to be a secret character with a formal reveal after the 3DS release. Shulk lining up with a more formal X reveal at E3 makes sense. I also don't think they'll keep a 3rd party character secret, so I think Pac-Man is about to be shown. I could see them showing off more veterans but I don't think it would be the ones people are expecting. Ice Climbers, if any of the other Pokemon Trainer pokemon are back.. these are who I can see happening. Characters like Jigglypuff, Ness, Captain Falcon, Ganondorf, Falco... are basically givens for secret characters. If Mewtwo is playable, I can see it going any way.. after E3 but before Smash release, after release of 3DS but before Wii U, or at E3. All these options make sense.