With the caveat that all characters are bisexual at the very least and obviously NO romance with underage characters under any circumstances:

Cid and Nero - So much sexual tension, they should have gotten a room decades ago.
Sadu and Magnai - Although they'd probably kill each other the first chance they got.
Lyse and Hien - I can kinda see them working.
Sadu and WoL - No comments there, one fiery romance.
Hien and WoL - Like a long distance relationship.
WoL and any of the Scions (barring the underage ones) - Thinking of the brave new Y'shtola here
F'lhamin and WoL - Lovely couple.
Cid and Thankred - One night stand.
Aymeric and WoL - Oh there's a potentially long lasting relationship that I see ending because the WoL is never there.
Aymeric and Lucia - Stating the obvious.
Lucia and WoL - Some potential there if Lucia can be persuaded to stick with WoL and become a Scion.
Feo Ul and WoL - I know Feo is already there for the WoL but I can just see them being romantically involved.

That's from the top of my head.