Does the option to build a palace randomly appear for rulers, like recruiting volunteers or moving the family home for Heroes? Does the option only appear in the capital? And will the option appear if a previous ruler already built a palace in that city?
Need a heap of gold on you too. I recall it appearing frequently when I had tons of gold on me, never otherwise.