A quick check of Memory Beta says that Arex's first appearance in the New Frontier books is in the short story compilation No Limits. He appears in the story "Road to Edos."
That's by in-story chronology, not publication order. Cold Wars, the book that added Arex and M'Ress to the cast, came out in 2001, while No Limits came out in 2003. Of course Arex wouldn't have been included in the anthology if he hadn't already been established as an NF character.
I haven't read it yet, but I believe at least Vale appears in the IDW TNG comic Hive. I know there were some pictures of a blonde woman who appeared to be Vale on board Titan posted somewhere not long after the the first issue with Titan came out. I'm not sure if any other identifiable Titan characters appear besides Riker and Troi, and it sounds like the story is completely incompatible with the novelverse.
That's right. The panel features Riker, Troi, Tuvok, a woman that the artist intended to be Vale, and an unidentified Caucasian male with a goatee. And yes, the story goes in a completely different direction from the novelverse. Its stardate puts its "present-day" portions in late 2382 (roughly between Paths of Disharmony and The Struggle Within), but the Borg are still around and Picard is still single, among other things.