Kanji or Yosuke
Teddie or Yukiko
Naoto or whoever?!?
Thanks yous =)

MC, Yukiko, Teddie, Naoto. 

Teddie: High damaging ice spells (especially with Snow Vow) + good damaging physical attack + excellent healing (Mediarahan...) + excellent buffs (Matarukaja...)  
 
Yukiko: High damaging fire spells (especially with Flame Vow) + ultimate healing (Salvation, status cure spells...) 
 
Kanji: intense damaging physicals + excellent buffs  (he's much better than Chie with physicals and much like Chie, his electric spells are just for knockdown purposes)

Teddie/Kanji/Yosuke is the only logical choice.

Yosuke: Awesome spells, wind is very important later game, and decent physical
Yukiko: Best healer in game also high magic.
Teddie: good backup healer, decent physical, amirita, and great ice spells.
 
So, that leaves the mc to cover electric and a bit later, dark/light.

My main party ended up being MC, Kanji, Yosuke and Yukiko.

My Team was Souji, Kanji, Yukiko and Naoto.

Play the game and choose the characters whose personality you like the best. It'll be more fun that way.

"

Teddie: High damaging ice spells (especially with Snow Vow) + good damaging physical attack + excellent healing (Mediarahan...) + excellent buffs (Matarukaja...)  
 
Yukiko: High damaging fire spells (especially with Flame Vow) + ultimate healing (Salvation, status cure spells...) 
 
Kanji: intense damaging physicals + excellent buffs  (he's much better than Chie with physicals and much like Chie, his electric spells are just for knockdown purposes)

"

I played the whole game with the original band:
 
Yosuke, Chie, Yukiko

Again the game is set up so you use all the characters and their SP and have the MC cover for what is missing.  You don't gain anything if you focus just on one party.  So use them all until the last dungeon or so.

I used everyone. Final Battle was Chie, Teddie, Naoto

"Play the game and choose the characters whose personality you like the best. It'll be more fun that way. "

Teddie - So loveable, and freaking amazing with his magic and support powers
Yukiko - In my opinion can potentially be the most lethal person in your party with her magic
Yosuke - Both of his garu spells and physical attacks can pack a whallop during the end game.
 
Also, I used Kanji, Teddie and Yosuke in my 2nd play thru, and let me say this. Teddie casting buff party defense, Yosuke casting buff party evasion, Kanji casting buff party attack and MC casting debiletate on the final boss is overwhelming powerful.

For me MC, Chie, Yosuke, and Teddie.  
 
I needed Teddie's buffs, healing, and powerful ice spells.  
 
Yosuke I just kept around for wind, evasion, and eventually physical attacks.  
 
Chie I used for just physical attacks. That first time using God's hand on an enemy with high defense made me say Holy fuck. The damage it did was alot. 
 
I never really used Kanji or Naoto. I stopped using Yukiko at about the 2nd to last dungeon.

Last two dungeons i used MC, Chie, Yosuke and Yukiko. 
 
Yukiko has really strong magic so her healing spells does a lot and her fire hits for a lot. 
 
Yosuke i kept for wind, evasion spell and his physical attacks did hit for a lot.
 
Chie was my tank, with party attack buff, power charge and then using God's hand she hit for so much.

I used Yosuke, Yukiko and Kanji. I think that party works out really well. Kanji is the game's only real tank, Yukiko is the best healer and offensive magic user, and Yosuke by the end of the game is awesome at everything.

" I played the whole game with the original band:  Yosuke, Chie, Yukiko "

" Yosuke: Awesome spells, wind is very important later game, and decent physical Yukiko: Best healer in game also high magic. Teddie: good backup healer, decent physical, amirita, and great ice spells.  So, that leaves the mc to cover electric and a bit later, dark/light. "

My party, i do not know if it is the best
 
Yosuke, Physical attack Brave Blade and Wind attack back up healer of the healer
 Naoto- Damager Mindcharge then Megidolaon which faces 567 damage if Rakunda and Tarukaja
Yukiko, usually Shadows are weak to fire and great healing.......
The other missing elemnts will be handled by the MC cause he gets to have multiple Personas ^_^

" I played the whole game with the original band:  Yosuke, Chie, Yukiko "

No Naoto. Seriously.

I went with all girls when I had the option to.

Persona 4 really isn't so challenging to the point where choosing particular party members is crucial to success, especially when you're just fighting random mobs. Certain boss fights will work much better with certain members (for instance, a lot of bosses like to cast elec so Teddie is generally not a good idea for higher level boss fights) especially considering that physical attacks are really the key to winning most boss fights, especially later on in the game. For regular mobs I'd go with Yosuke, Teddie, and Yukiko/Naoto. All three have high-level elemental attacks and good buffs. Naoto and Yukiko are pretty interchangeable since you already have Teddie for healing purposes and Naoto can be pretty useful given that she has learned her all-light/dark skills. Kanji and Chie are unfortunately ill-suited for random mobs since a.) Kanji does not learn all-physical skills and has poor elec skills (due to his low magic stat) b.) Chie has only low-level ice skills and won't get good all-physicals until later on in the game (well rampage is pretty decent but that's about it until agneyastra).
 
For boss fights, the best combo is almost always Kanji, Chie, and Yosuke (at least in later dungeons; in earlier dungones Yukiko is probably a better choice than Yosuke). One reason is that their persona have no weaknesses when you s-link up to 10 with them (as said before Teddie's elec weakness can be pretty dangerous and even Yukiko's ice weakness can be annoying at times). The other reason is that they learn the three best single-enemy physicals in the game (most bosses don't have elemental weaknesses): God's hand, brave blade, and primal force (it is unfortunate however that Yosuke doesn't learn any physicals between sonic punch and brave blade). Chie also has Power Charge (though Kanji can do more damage with 2 primal forces vs. 1 power-charged god's hand) and Kanji also has matarukaja, which is pretty essential against most bosses. Of course this means that you'll have to do most of the healing, but since you have the best ways of recovering SP, that shouldn't be much of a problem.

All right thanks to everyone who replied I think I finally know who to choose now =]
I'll go with...
Yosuke, Yukiko, and Kanji!
Thanks for all the suggestions!