I wouldn't take lore considerations based on early levels into account. After release my group consisted mostly of Gale, Shadowheart and Lae'zel, later I replaced Gale with Astarion when I tried magical classes. Currently my group is Shadowheart, Gale and Wyll, and that will be the party at release most probably. I don't see big differences in the experience of the story. I think Larian is clever enough to make it more or less the same whatever you choose.
For me it's important wether I "like" the companion (wether he/she is nice or interesting or, er, wether I want to sleep with him/her ...) and wether I like playing the class (as you necessarily have to play the three companions in tb combat). For example I don't like rogues, so Astarion is not in the party, even if he seems to have an interesting background story.
