Hmmmm seems like I have alot to think about.
My build for the bard would be focused on buffs and bardic music, taking the extra music feat and maybe lingering song. He would probably use a longspear and standing behind the fighters, in the middle of the group providing some reach attacks and good positioning for buffs and the like. He would be the mouthpiece and the source of information, knowledge and lore (I like those aspects).
My build for the paladin would be like the bard in that he would probably use a reach weapon like a glaive and provide that mid battleground support. I would take the charging smite ability from PH2 and probably the divine feats associated with expending turn checks for healing.
On the one hand I think the bard may have some additional tactical options (e.g. use magic device) but I worry that his musical skills (e.g. fascinate) may not come in to play too often, leaving me a relatively weak combatant with relatively weak buffs in a brutal meat grinder.
The idea of a second cleric is also a good one, perhaps one that focuses on buffing (himself) to help out in battle and provide clutch healing when necessary.
I guess what I need to know is whether Shackled City is an absolute meat grinder of doom. If it is, I think the paladin is going to edge out the choices.