The cave for Jonaleth's quest is after the harbour (channel to the south), and is specific to this particular quest. The one for Barbatos is before the harbour (before where the barrier was, actually), in a cave where there is other stuff to do and a solution to another quest.
Thanks! I found Jonaleth's, which is easier. Now I guess I have to go back and search all the old caves for the other one. Any other subtle hint you can provide?
Edit 1: There is a cave door directly across from High Hall, which I have already explored and now the door is locked. That's not it, is it?
Edit 2: Nevermind, I found it! I actually had never been there before, but I studied my map a bit and noticed the different colored section and went to check it out. I can't believe I never saw that door before! Now all I have left is to find the first adventurer. Let the hunt begin again...