True, the palace is only fluff, but thats true for wonder screens/movies too!
And the purpose of the entire game is nothing more than entertainment.
To the OP:
The first palace improvement pops up after pillaging your first barb camp.
There are more of these rules, but I don't know most of them. I think most of the time its a first time you succeed at X rule. Just like the barb camp one I mentioned above.
Building your 2th city as Nergal stated, has no effect as far as I know. I usually expand very quickly, and have many cities before I bust my first barb camp most of the time.