Inspired by Rodrig0's thread inquiring about Palace Upgrades, and the apparent communal bewilderment about the topic, I set about determined to investigate ways to maximise my Palace building. The results will astonish and amaze you as some quite unexpected outcomes made themselves evident.
So, without any further ado, here's Buttercup's guide to getting that Palace up as quick as possible. You will require 17 upgrades for a full Palace:
1. Founding your second city.
2. Your Capital gets to size 10.
3. Your Capital gets to 1000 Culture.
4. Your entire civ gets to 5000 Culture.
5. Your 11th city gets to 100 Culture.
6. Your second city gets to size 10.
7. Being the First to Enter the Medieval Age.
8. Your 21st city gets to 10 Culture.
9. Making a Military Alliance.
10. Reveal every last inch of the Map (you do not need to be first AFAIK).
11. Have all 8 Luxuries either by ownership or trading.
12. Your Capital builds it's 5th Wonder*
13. Your second city builds it's 5th Wonder.*
14. Being the First to Enter the Industrial Age.
15. Making a Mutual Protection Pact.
16. Your 11th city gets to 1000 Culture.
17. Your Income gets to 500.
18. An enemy civ attacks one of your cities (also includes Barbarians) for the first time.
19. Being the First to Enter the Modern Age.
20. Completely defeating a rival civ for the first time (either capture or destroy last remaining city).
21. Your Capital city gets to 20 Citizens
22. Your second city gets to 20 Citizens.
23. Have all 8 Resources either by ownership or trading.
24. Your Capital city is remarkably happy (relates to We Love days, but may occur without "We Love" visibly triggering).
25. Attain your first monopoly of one Luxury, all existing examples of the Luxury appearing in your trade window.
26. Attain your first monopoly of one Resource, all existing examples of the Resource appearing in your trade window.
27. Trade out (not in) a Luxury for the first time to another empire. (requires a specific condition).
28. Unknown reason caused by building a random Wonder (possibly relates to favoured Wonders by trait - speculative).
29. Destroy your first Barbarian Camp (extremely temperamental? Requires a specific condition, like 'first to' or something?).
*I have built 5 Wonders in my Capital and got an Upgrade. I have built 5 Wonders in a random city and got an upgrade. I have built 5 Wonders in both my Capital and 1 random city and got two upgrades (one for each). I did not get an upgrade for building 5 Wonders in a third city. I have not tested if one of the upgrades requires it to be your Capital or if you can get both the upgrades from two non-Capital cities, but Capital+1 fits with other upgrades.
When you suddenly get two or even three Upgrades, it's not necessarily a bug of delayed Upgrades, but often some of the above occurring simultaneously, such as your 5th Wonder triggering a Golden Age which suddenly zooms your Income over 500 and makes your Capital really happy
.
Found using Civilisation 3 Complete, Regent Level, Huge Map, Archipelago, all middle settings, 11 opponents, all usual Victory Conditions. I have tested these in many, many games.
There are more ways to get Palace Upgrades, this is not an exhaustive list and I welcome any new confirmed additions, but, as you can tell, by the time you get to Nationalism you will probably have a full Palace, so won't have any idea what after that triggers an Upgrade. I shall continue to investigate for more Upgrades by trying to manipulate my games to avoid some of the above.
And we now have a new, never before tried by anyone, max'ing challenge for all you civ'ers who are looking for a new twist:
I just finished a game where I maxed my Palace @ 1200AD exactly, one tech into the Industrial Age (Nationalism). Now, I know I could have been quicker as I couldn't hook-up all 8 Luxuries in this game because the nasty ol' AI only gave the game one solitary Gem square, so I'd have to have invaded a whole civ to get it, by which time in my game hanging out for Nationalism was quicker, but I 'should' have max'ed by 1050AD if there had been more Gems.
So what are you waiting for?
Get adding to my list or max'ing those Palaces...
Feel free to ask any questions.

So, without any further ado, here's Buttercup's guide to getting that Palace up as quick as possible. You will require 17 upgrades for a full Palace:
1. Founding your second city.
2. Your Capital gets to size 10.
3. Your Capital gets to 1000 Culture.
4. Your entire civ gets to 5000 Culture.
5. Your 11th city gets to 100 Culture.
6. Your second city gets to size 10.
7. Being the First to Enter the Medieval Age.
8. Your 21st city gets to 10 Culture.
9. Making a Military Alliance.
10. Reveal every last inch of the Map (you do not need to be first AFAIK).
11. Have all 8 Luxuries either by ownership or trading.
12. Your Capital builds it's 5th Wonder*
13. Your second city builds it's 5th Wonder.*
14. Being the First to Enter the Industrial Age.
15. Making a Mutual Protection Pact.
16. Your 11th city gets to 1000 Culture.
17. Your Income gets to 500.
18. An enemy civ attacks one of your cities (also includes Barbarians) for the first time.
19. Being the First to Enter the Modern Age.
20. Completely defeating a rival civ for the first time (either capture or destroy last remaining city).
21. Your Capital city gets to 20 Citizens
22. Your second city gets to 20 Citizens.
23. Have all 8 Resources either by ownership or trading.
24. Your Capital city is remarkably happy (relates to We Love days, but may occur without "We Love" visibly triggering).
25. Attain your first monopoly of one Luxury, all existing examples of the Luxury appearing in your trade window.
26. Attain your first monopoly of one Resource, all existing examples of the Resource appearing in your trade window.
27. Trade out (not in) a Luxury for the first time to another empire. (requires a specific condition).
28. Unknown reason caused by building a random Wonder (possibly relates to favoured Wonders by trait - speculative).
29. Destroy your first Barbarian Camp (extremely temperamental? Requires a specific condition, like 'first to' or something?).
*I have built 5 Wonders in my Capital and got an Upgrade. I have built 5 Wonders in a random city and got an upgrade. I have built 5 Wonders in both my Capital and 1 random city and got two upgrades (one for each). I did not get an upgrade for building 5 Wonders in a third city. I have not tested if one of the upgrades requires it to be your Capital or if you can get both the upgrades from two non-Capital cities, but Capital+1 fits with other upgrades.
When you suddenly get two or even three Upgrades, it's not necessarily a bug of delayed Upgrades, but often some of the above occurring simultaneously, such as your 5th Wonder triggering a Golden Age which suddenly zooms your Income over 500 and makes your Capital really happy

Found using Civilisation 3 Complete, Regent Level, Huge Map, Archipelago, all middle settings, 11 opponents, all usual Victory Conditions. I have tested these in many, many games.
There are more ways to get Palace Upgrades, this is not an exhaustive list and I welcome any new confirmed additions, but, as you can tell, by the time you get to Nationalism you will probably have a full Palace, so won't have any idea what after that triggers an Upgrade. I shall continue to investigate for more Upgrades by trying to manipulate my games to avoid some of the above.
And we now have a new, never before tried by anyone, max'ing challenge for all you civ'ers who are looking for a new twist:
I just finished a game where I maxed my Palace @ 1200AD exactly, one tech into the Industrial Age (Nationalism). Now, I know I could have been quicker as I couldn't hook-up all 8 Luxuries in this game because the nasty ol' AI only gave the game one solitary Gem square, so I'd have to have invaded a whole civ to get it, by which time in my game hanging out for Nationalism was quicker, but I 'should' have max'ed by 1050AD if there had been more Gems.
So what are you waiting for?
Get adding to my list or max'ing those Palaces...
Feel free to ask any questions.

