As a Water nation and playing against AI only, you aren't in such a hurry. Take a few turns in the beginning so that you can take on those annoying flying Tritons. Then try to use that one army to take few surrounding provinces, all the while building more units in the capital and sending them in as reinforcements. Doing this, you should be able to conquer the provinces around your capital about one per turn once you start. (but only take land provinces if you can do so easily and they will be worth it). If your army is tough enough now, it can move forward; if not, wait for a turn or two and then continue.
You have to minimize losses you take, by either using units you can afford to lose (e.g. Lobo Guards and not Shambler Thralls - both die a lot, but LG are much cheaper) or by killing your enemies before they kill you.
Try to recruit one mage or priest per turn, and have them research Thaumaturgy. Mind Burn at Thaumaturgy 2 is already quite interesting, and later you will get Paralyze (spell-equivalent of Mind Blast), Soul Slay and then Enslave Mind.
The Starspawn priests are the only creatures who can enter the Void Gate with some possibility of getting back sane. Luck scale affects the amount and power of creatures coming back.