Brawl totally needs
Mia,
Jenna,
Sheba, or
Karst from Golden Sun.
Mia is a healer who fights with water/ice elemental attacks, and Brawl could definitely use more non-fire elemental characters. She also has the closest tie to the main villain in the game and helped you enter the first elemental lighthouse.
Jenna uses fire. Although there is certainly a lot of fire in SSB games, most of it is just an extra effect (e.g. Roy and Falcon) or it's the fire breath move (Bowser, Charizard, pokeball pokemon). No character really makes full use of the element. I could see her using staff- or sword- or mace-based and casting attacks that make full use of the range fire would provide. Also, she is an important character in both games, as Felix's sister and Isaac and Garet's friend in Vale, she was playable in the beginning of GS1, and she was also the first playable character in GS2.
Sheba is a telepathic girl who fights with wind and electrical attacks. That combination could make for a very unique fighter. Also,
Catastrophe would be the most awesome final smash ever. She was a mysterious girl who was kidnapped in the first game and then became playable in the second.
Karst fights with a sythe, and Brawl is completely lacking in the sythe department. She was one of the main thre antagonists in GS2, and she has ties to the main antagonists in GS1.