When I last left off, I had played the game without starting a war on my own, but had twice been attacked by Rome. I captured Antium from him, and then took peace in order to build some more catapults and start work on X-bows. As JC is the only heathen on the continent, even when I went to peace, he was still fighiting off stacks from Izzy and Khan.
Since the time of the first Roman attack, the strategy has been to eliminate him first, which would move me from 5 cities to 10. Next would be Sitting Bull, and then it would be time to evaluate the situation.
By the way, despite being industrious, I only built Stonehenge early on. With the strategy to pretty much be fighting the whole game, I made sure to divert some hammers in Thebes to build the SoZ, which has been a really good thing to have on my side. I also built the SP, as any wonder that lets me change civics freely works really well with the Spiritual trait. I have spent a lot of time flopping back and forth between Theocracy and OR.
In order to pull off my military goals of Rome then Native America, I have been VERY friendly with Izzy and Khan, and cordial with Sitting Bull. I also needed to run a few specialists to help with research, as I've researched almost entirely along a path to win wars. I went Machinery, Engineering, Civil Service, Gunpowder, Guilds, Chemistry, Steel, Military Science. I think I researched a couple others, plus I bulbed a thing or two. Everything else I picked up in trades. I saw very early on that cannons would be the key to victory if I got them before Grens or Rifles hit the board.
Strategically, I was able to build a bunch of Trebs and with swords, axes, crossbows, a pike or two, and war chariots I attacked JC sometime before 1200 AD and took him off the board well before 1400. Wonderfully offsetting the expensive addition of several established cities, was the fact that Rome contained the Pyramids. I went DIRECTLY into representation and started running scientists. As soon as JC was dead, which went very smoothly once the trebs showed up, I flipped into Organized Religion and started building courthouses and tons of AP religion Buddhist temples and monestaries.
After that was done, I started building military again. In or around 1600AD, I discovered steel, and upgraded as many of my 15-20 trebs as I could in 3-4 turns. I moved them, along with a dozen each of muskets, maces, knights, as well as 15 assorted older units including some crossbows and a bunch of CRII or CRIII swords and axes (waiting for plunder to be upgraded to maces) up to the edge of Native American territory and launched my invasion.
Somehow, Sitting freakin' Bull had Steel as well, and as I was steamrolling through his first city and heading for the captial, he launched an impressive cannon heavy stack into my territory and actually captured Memphis from me. This was annoying, as Memphis was a nice commerce city and had a lot of culture generating from it as well. On the other hand, it took very little effort for 4-5 of my cannons and my temporarilly redirected stack of knights to recapture the city and pretty much destroy any chance of him recapturing any of his own cities. As we all know, cannons capture cities really well, but leaving ten of them in there to defend it is really stupid.
As of this update, Sitting Bull has three cities left, two of which will fall within the next three turns, and the last will be gone shortly thereafter.
The other two civs and I are Friendly. Technology is in pretty good shape with those two, although they are both pretty far along some lines I've completely ignored. Most importantly, I don't think the Mongols are anywhere near steel or Military Science, which means that I could probably do some serious damage to him right now, if I choose to do so. If I can figure out how to raise the gold, I could upgrade an awful lot of units to CR Grens, which would just slaughter longbows and muskets in combination with cannons.
As for the other continent, I just sent off my first caravel and ran into Justinian. He's middle of the pack score-wise, and since he has yet to meet anybody on my continent, I made a tech trade with him giving him something like gunpowder, paper and some scratch for Nationalism. This puts Military Tradition in play, and I should seriously consider it next. MT most of my knights are level four (Rome had three settled GGs, and has been building mostly 13XP knights for the last 70 turns) so they would all upgrade to very powerful units should my next target also have stacks of cannons.
So it hasn't been easy, and it probably will continue to be a slugfest, but an all-out war strategy seems to have been the best way for ME to get a victory on this map. There were simply too many other civs on this continent for any sort of peaceful expansion strategy to work efficiently. The existence of religion hoarders and warmongers made a cultural victory seem highly unlikely. As far as I can tell, my experiences with the prince level have pointed me to towards a military strategy, BUT with the notable differences of being willing to trade military techs to backfill and the conscious decision to build A LOT more units than I would have done at the lower level