I usually play Monarch difficulty, version 3.5, with Revolutions (an unbalanced 3.5 feature) and vassals off, on Standard to Large map size, default realistic speed. I've found Monarch difficulty to provide a good equilibrium of challenging but winnable games. Maps are Perfect Mongoose, RI EarthEvolution or Planet Generator.
Somehow it feels as if the AI never suffers any negative consequences from creating mega cities, whereas I have to fastidiously keep my growth in check, only to find my rival(s) happily working with a pop 15 capital and 5+ cities at 11-17 in the medieval age. Does the AI not get the debuff from pandemics or something? This applies to number of cities as well. The AI does not seem to suffer any increases to research time if it has a bunch of cities. Although Civ IV was designed to eliminate infinite city sprawl the AI seems to employ it with impunity.
At Monarch and above the AI gets pretty significant advantages. Part of having more cities is having more luxury resources, leading to bigger city caps, but the AI also just straight up gets to have more and bigger cities. This is something you'll have to live with. The AI is affected by reduced tech rate from growing too wide as well, but they can usually deal with it.
Not overexpanding and keeping your tech rate up is important. Being relatively isolated on a continent with few competitors early on can also be detrimental, as you want open borders with as many people as possible for tech cost reductions.
Part of not overexpanding is picking how to expand. Conquering one or two capitals or otherwise greatly positioned cities in the classical/medieval ages is better than founding in all those mediocre city spots you have near you. Early on you want each city you have to be as good as possible, there's no room for "I guess this one pays for itself" cities. So found one or two, then go on the offensive. Don't hesitate to raze. The downside of this is that you usually don't form a contiguous empire, leading to border gore and there being no safe "backyard" cities.
Essentially I feel like there's some trick to generating research
Like already mentioned, stacking Great Scientist wonders. The AI likes to do it too, which is often how one particular one gets ahead.
and healthy growth in the early to mid-game that I'm missing.
Up until Free Market and the loads of cash that civic usually nets you gradual growth seems to be the answer. Don't be worried by civs having higher score or being larger than you, it's only an issue if they have a tech advantage or are really overwhelming with their armies or there's a bunch of AIs taking turns invading you.
1. Is there ever any point in running Protectionism? This civic utterly baffles me.
It's pretty good when the situation is right for it, just most of the time the situation is right for Free Market instead. Basically you want to run Protectionism whenever there aren't good foreign trade partners. You can see the share of internal/external trade income in the info tab of the foreign advisor window. Especially later when you are dominant and the only two or three remaining large competitors hate you it can be advantageous to switch, either to Protectionism or Planned Economy.
2. Does the AI ever use GPs to research techs or run trade missions?
I've at least never seen them run Great Merchants through my territory.
3. What leader traits do you think is best?
I'm a fan of Seafarer for the +1 trade route. Financial, Industrious, Progressive and Spiritual are otherwise preferred picks of mine. I've seen people diss the free promo traits like Conqueror, Militaristic (aka. Aggressive) and Protective, but I like them - a big part of winning wars is trading losses well on the battlefield, losing 1 unit for every 1 unit killed puts you on the back foot, not only aren't you making progress and wasting time, but the AI also has an easier time building units than you. Having a core of highly upgraded units is what wins wars, a City Raider IV Man-at-Arms does the job of an entire stack of levies and costs less to maintain. That extra upgrade or XP gets you there much earlier.
4. What's the optimal balance between growing towns and growing GPs?
I wish I knew!
Edit:
Some other general thoughts:
Unit cost is the biggest expense I have in the classical and medieval ages. Maintaining a large army is often a simple necessity (think you have enough units? Build a few more), but it can cripple you. Especially devastating to my economy/tech rate I've found situations where I fight a slow war against a competitor, sieging cities over dozens of turns while slowly build up enough units to storm them, paying lots of maintenance and supply all the while. A key takeaway here, aside from not getting mired in long siege wars, is to avoid attacking enemies with a defensive advantage. That means cities on hills, typically. Hills are very important. Also, try to time invasions to happen before an enemy researches the 4-str Bowmen from Iron Working or Longbows. Be aware if the target civ gets crossbows or longbows (or both!) and plan accordingly. I've attached a file that lists the different units civs get, not sure where I found it anymore.
Cavalry and Skirmishers are defensive units. They aren't typically of much use assaulting cities, but very effective in assaulting stacks in the field, such as those invading you. Train them up on barbs and slave/serf revolts.
Naval fighting is much more of a simple material battle where, assuming equal tech, each side's production is worth largely the same, for the lack of significant defensive/offensive advantages. This only really changes with industrial era Pre-Dreadnoughts and Light Cruisers which introduce a rock-paper-scissors mechanic. Since you'll have to spend roughly as much hammers as the enemy that means you're automatically at a disadvantage because the enemy gets cheaper hammers than you. Consider just conceding the water and focusing on land, if that's an option.
On the other hand it can be very nice indeed to catch and destroy an incoming invasion fleet (and all the land units loaded onto it) before it even reaches your shores, but that requires a suitable map where you don't have too wide a range of shores to defend and the enemy comes from far enough away that you can spot and catch them in time. Given the need to scout far out on the ocean, have a large fleet and being able to bring it to bear at any point on your shores within a turn or two's time (typically meaning multiple large fleets) and the need to declare war on your would-be invader first (a diplomatic disadvantage), this is very hard however.
