This is all from theory-crafting the champion so we will need to see what comes out of actual play, however there are two main interactions with the support.
Firstly we have Soul Marked
Soul-Marked - Passive: If Kalista and her Oathsworn ally attack the same target within 1.5 seconds of each other, the target will take additional magic damage equal to a percentage of their maximum health. This effect cannot occur on the same target for 8 seconds. Damage is capped against minions and monsters.
This generates extra poke each time Kalista and the support both attack the same target
The obvious point here is that a ranged support would be excellent as you can stack together your poke on the same target. For a melee support this particular passive will be less impressive although it will still help on all-ins.
Secondly we have Fate's Call
During Fate's Call, Kalista's Oathsworn can right-click a target location to dash there, stopping at the first enemy hit, knocking up all surrounding enemies and landing themselves at their maximum attack range from the target.
Fate's Call disables the support's abilities for 4 seconds, so they will probably want to wait until near the end of the 4 seconds before going on. This will place them on top of the enemy team so you now want champions that can take advantage of this. Obvious choices are:
Morgana, this seems like it should be a really strong combination. You have the range to benefit from the poke passive, while at the same time having an ultimate that benefits from being in the middle of the enemy team. Additionally the knock-up will make it harder for them to avoid the stun at the end of the ultimate.
Janna, flash+ulti will throw the enemy team in all directions and some of them into your team to be picked off.
For both of these though the fact that you land at your maximum attack range weakens the combo considerably though, it gets you close but it may not get you close enough. On the other hand however it does make it less "all or nothing".
Leona, she can land her stun at close range and save Zenith Blade to follow anyone who flashes or uses an escape.
Amumu, similar to Leona, in the middle of their team lets you land an awesome ultimate and you can also follow a fleeing enemy with bandage toss.
There are a number of other champions that offer similar abilities too, Thresh's Box, Wukong's ultimate, Alistar's, knock up. Essentially any champion that thrives on being in close to the enemy team and that is able to lay down the pain.
One interesting possibility here is that if you have a melee support then you have already sacrificed the Soul Marked passive for poking (although it will help on an all-in). In that situation it might even make sense to form the bond with something like a Jungling Amumu. Use your ultimate to pull Amumu in then throw him at the enemy laners, he can then Curse of the Sad Mummy and follow any that get away using Bandage Toss.