I'm still playing on King. Which I grant you is a bit of a walk over in the mid to late game, but I've stuck with it because I still have misfires in the early game, and sometimes an AI will go into runaway even at this difficulty. Anyway, unless I'm fairly isolated, I find that I'm almost always going for an archer rush on my nearest neighbor. One or two warriors, 4-5 archers, with the archers doing the vast majority of the damage. With just about any civ. Sumeria's an exception because of warcarts, but few of the early game special melee units are strong enough to support a rush. I just tried playing Monty for the first time, and my 5 Eagle Warrior rush against nearby Greece completely stalled out because Gorgo got city walls up. While that's bad news for any Ancient era rush, it's particularly bad when you're all-melee and doing only a couple of points of wall damage with each attack. I think I would have done better to go with my standard mix of mostly archers, despite the strengths of the Eagle Warrior.