If the pace feels too slow, perhaps playing on Fast would be good for you. Increasing movement would unbalance so many factors, it is probably a non-starter with the devs. I like the movement pace. For me, on normal, all pace is really quite good. The early game, it should be noted is an RPG more than TBS. They certainly have not struck the perfect balance of how that should play out, but this new version plays much better than anything else we have seen. 

I play on all normal factors with a Challenging AI. Middle of the road all the way for the sake of beta testing. I play on a Temperate map or a Balanced Map. I play as Kraxis. If you think the pace is slow, play with 1000 Gildar to start. I can get many many heroes working together and rush some bonuses to research. Exploration is the name of this RPG. You have to get out there, get the early items, and find some research bonuses. Scouting for resources is good too, but mostly research is what I look for. That and easy monsters to level my bands of heroes. By about turn 60 I am pretty much done exploring in RPG style and can really get down to the expansion phase. This is where the game is intended to play more as TBS.

What settings do you use? Which factions? What is your starting strategy? Time to compare if we are getting such different results. My let's play videos are taking forever to upload to Youtube, otherwise you could look at them for comparison.

My first impression was that pacing was great for production, but abit too fast on research. This is playing normal speed. Researching the first military techs goes so fast you can have a spearman in leather ready to be produced after building a first building and a pioneer in the capital. No reasons to make the first military techs free, they make you have to choose harder in the start what to research first. The only prob is it's kind of a non brainer choosing the 2 first military techs first. Civilization tech will give you buildings you dont have time too build in a while anyways, and the 2 first magical techs can also wait, no need to rush them.

I don't feel I have to little to do when it comes to exploration and securing territory either.

Conclusion: Slow down the tech speed abit on normal, keep the pace as it is otherwise. This will make the tech choices harder. Now I find myself rushing the tree all too fast.

Trying epical the research speeds was all to slow compared with the fast production speeds. Here production times should be made slower. Perhaps make a marathon speed too, so epical can be something in between.

The intention is to make you have too choose. Earlier units, or getting those ressources early. You decide if you want to slow down the building of the new units. You can build them as early as before on the cost of getting the ressources later. It's great and give us more hard choices, I'm sure you like that.

I agree that the slow movement is a major factor. I have always wanted more strategic movement for Champions to facilitate exploration and questing,  while armies have to move slower. I would like to see strategic movement doubled for Champions.

Right now, pioneer spam is the main pacing problem I see. The AI can and will throw out pioneers like crazy with no repercussions. Rapid expansion should be a choice that provides the advantage of securing more territory, at the cost of greatly slowed development. Wide vs. Tall.

early pacing was fine for me in my first game on normal speed.  I like the RPG-like stuff before the empire building comes.  that said, maybe there could be a "quick start" option?

one way to help the explore part might be starting out with a talent or just plain free scout? I too feel scouting in the start of the game is pure pain due to slow, blind units, and all these forests and hills makes master scout really powerful for scouting...

Might wanna try to play "Tarth", meaby a version of Magnar where his faction have the Master scouts ability (Cheap slaves and more movement).

Sincerely
~ Kongdej

Depends on which faction you choose. Gilden is better off sometimes with Battle Hammers to start. Some warlike factions are better off with spears first. It just depends on your starting location. If you are lucky and get a 3/4/1, go for spears and start leveling some armies. The gildar from killing is usually enough to support your economy for awhile. Magnar, for instance are better off getting spears and leather as the other guy said. You will level fast enough with those slaves to get way more than +1 Prestige. And since he doesn't get Wells or the upgrades, no reason to go after civics until much later.