The cave you are looking for is the one just past the Troll's Bridge, the top right-most icon if you are looking at the world map, and for the husband for that lizardess, he can be found by exploring the Forgotten Temple until you trigger a scene about him with the female lizardess and the warriors on the stage.