If I were you I would go with Pokemon Trainer. While the Shiek and Zelda combo is good, I think it will waste to much time switching bwtween them both.
That's my two cents. I'm gonna go with Ike. Hard hitter for the 4 minute matches and my best character for one on ones. If for some reason I decide not to go Ike i'll probably go Metaknight. He is just so fast.