Thinking about this today, I guess it's a question of what's meant by "agent of the divine." In a sense, she's an agent of Dorothea, who's the future Divine, in Leliana's Song, which takes place before Origins. She likely wasn't known as Dorothea's "left hand" then, but I doubt "left hand of the divine" is the sort of title that goes on resumes and business cards. It's not an official title.
And it's not like she or anyone else could have been the agent of the previous Divine, Beatrix. Beatrix was beyond knowing or caring what went on in the world by the time Leliana entered into the picture. She herself was basically just a hand holding a rubber stamp while other people made church policy from the shadows.
Was Leliana a Seeker then? For that matter, is she a Seeker now? We've seen her wearing the uniform in 9:40 Dragon, but we've never seen her use the Seeker talents. When she dealt with mages in the Faith sidequest in 9:37 Dragon, she preferred double daggers to disrupting their spells.
So we know she's always been working for Dorothea, at least informally, but when did "working for Dorothea" become "working for the Chantry"...? That is, when did Dorothea replace Beatrix as the most powerful person there? Was she always the hand moving the rubber stamp? Or did she have to shove someone else out of the way to get there?
One interesting detail: you can play Mark of the Assassin at any time starting from Act I, and Leliana is always at the party. She's the person Cassandra is referring to when she says "We had someone there, but they lacked your Access." They put a lot of thought into reactivity in MotA, changing dialogue depending on the act you go there. Well, if you go in 9:31, Leliana would basically have had to have come the same year the Archdemon was killed, which would have meant she was acting on behalf of the Seekers three years before Dorothea officially took power 0_o
That puts a fascinating spin on Dorothea's rise, and who was really running the Chantry while Beatrix was losing her mind.
As for Leliana's honesty and sincerity, if we take Leliana's Song as canon, then there's already things she left out - and even in the main story of DAO, she comes to you as an innocent sister, and then admits she's a trained assassin who's killed people. But we don't have to see her as insincere in her beliefs. Like a Hawke who practises blood magic toward a good end, or a Warden who lets Prince Bhelen have the anvil because the Archdemon winning is worse, both Leliana and Dorothea seem to have true faith but believe that the end of that faith justify certain brutal means. They are both ex-bards.
And it's not like her patron is any stranger to unorthodox religious beliefs. She's the first pro-mage Divine, and was willing to risk war with her own Templars to help mages or moral principle. I imagine someone like that would be quite sympathetic to Leliana and her vision.