Way I see it (listing the sense-making ideas and the listed ones that I know something about):
Elincia and Mist
+ Female character
+ Unique Weapon set (Staves aspect, not Swords)
+ Relevant and recent game
- More freakin' sword users
- While plot important characters, not actually the main lords
- Popularity in question
- Both are technically Mounted units, Mist less so than Elincia
Micaiah, Sanaki, and Soren
+ (M and Sa) Female
+ Magic users, nothing like the swordsmen we already have and assume
+ (M and Sa) Main characters
- (Sa and So) Not actually main lords
- Soren is only somewhat plot important
Black Knight
+ Bad@$$
+ Plot important
+ Villainy
- Sword user
- He'd have to be SLOWER and STRONGER than Ike to be correct, that'd be tough to do
Mia and the other Swordmasters people want
+ One of the most favored classes
+ Mia is recent and somehow on Sakurai's list
+ Definitly not like Ike or the other Lordling sword weilders
- Still a Sword user
- In no way important to the plot
The Axe twins from FE1
+ Axes aren't swords
+ One spot for two characters if done right
- Not really plot important
Sheeda
+ Romantic interest for Marth, Peach to his Mario and what not
+ Female character, decently plot important
+ FE1 is being remade
- SWORD USER
Sigurd
+ Popular
+ Plot important... sorta
- He's not actually the main lord
- Marth + Ike + Sigurd = Too many blue haired sword weilding lords in one game, totally skewing the reps for FE to one side.
- Again, Sword user...
Personally, save for the Axe Twins and Sigurd, I'd be fine with any of the others in Brawl. If I had to organize them into an order of personal preference:
1. Mia/Wayu
2. Mist or Micaiah
4. Black Knight
5. Elincia or Sheeda
7. Sanaki or Soren/Senerio