[Taqwus]

A possible R'lyeh theme would be 'dreamtime' -- prior to the awakening and their very public emergence. Make it into a stealthy, less direct nation more reliant on often-stealthy cultists. ConVersion might be yielded through commander order, spell, or perhaps even dominion or global. A Feeblemind-causing aspect for the remaining Things would not go amiss.
Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn.