I enjoy it with 4P, and would even play 5P if asked, but the sweet spot is 3P.
As you add players, you are more and more likely to get screwed by opening an area. Odds are good that advisors will be placed, and with the higher player count, there is less chance of any one player having enough cloisters to open up more positions for advisors. It becomes a game of avoiding opening new regions and just joining the bandwagon to fill what is already open. This happens with 3P, too, but there are more decisions of when to open something new that you will be able to take advantage of.
And, yeah, unless you're dealing with some terrible AP, this should play out within 30 minutes after the first game or so.
