I like Grogtank's Research Order, with one alteration: Horses are an absolute must! 4th tech I get (well, 5th, technically, because of Training) is Horse Riding. Then I go to town on the Civilization tree, sometimes picking up Archery mid-game and sometimes not bothering.
I was initially playing a lot on Easy, but now I've progressed to Challenging, and I can still easily ROFLStomp the AI fairly early on if I feel like it (in my current game on a Medium map with 3 AIs, Magnar pissed me off by ninja'ing monster loot on me, so I ground them to dust as penance = P). It's harder on random maps, yes, but if you solely play pre-generated maps (Bay of Capacea and Anthys are very good choices for map control), it's fairly easy to memorize the layout and know where to cut the AI off so it can't expand.
To clarify that point: Find narrow choke points (preferably 1-3 squares wide, wider if you must) and plug them with stacks of spearmen or other cheap units. The AI can't get through them (even with a NAP!) and thus you can severely control where they go.
It's also very, very helpful to make a custom faction with Mancer race, Master Scouts, Arcane Monoliths, and whatever else you desire (Archers is an excellent choice, as ranged units own early game, and with Archers, they also own late game). Start yourself off with a Conclave on a good 2+ essence spot and forge a little bit into the Magic tree to maximize your mana/turn, so you don't have to waste Pioneers on Outposts. Makes a WORLD of difference early game. Mancer + Master Scouts + Horses means 5 moves per turn, no terrain penalties, excepting recruited heroes from other races.
You can also possibly improve your chances by making the Research pacing Normal or Epic (assuming you don't already have it there) and your Build rate Very Fast. This pretty much lets your construction keep up with your research, reducing that feeling of being pressured into, "do I build improvements or do I train troops?!"