If you let Gremio die (and Pahn) then besides Cleo you've got long standing allies such as Camille, Humphrey, Lepant and his family, Luc, Kai, Kirkis and his elves... Depends on how you play and who you become attached to. I pick Valeria as one of my old allies even though she doesn't do much in the story once you've defeated Kwanda, but I favor her in S2 as well over ninja-minge.
Humphrey is one of the original liberation army members, along with Viktor and Flik, so I like using them as a trio. I often bring them all together for the end of Suikoden 2 as well (they do often sit drinking together in Leona's tavern)
From the early recruits in S2 I like to use Rikimaru, Kinnison and Shiro a lot. I know kinnison is not exactly final dungeon material compared to a lot of characters who join later, but I don't like to separate Kinnison from Shiro (and why not have a wolf fighting a giant 2headed wolf?) and I like to imagine him becoming good buddies with Riou.