There are so many different spells and skills to choose from that I'm having a hard time finding which ones exist to support different strategies. Early on I'd like to focus on skills that either directly or indirectly make my hero level up faster (trying to slingshot into some of the higher level skills). What skill choices exist to help me do this?
The only skill that directly supports levelling up faster is Enlightenment, as mentioned by Raven Dreamer in his answer. As far as indirectly making your hero level up faster, you want skills that make it faster to defeat wandering monster stacks, as that gains you the experience for winning combat, as well as access to any treasure chests or artifacts the monsters are guarding. Depending upon the design of the map, it may also open up the map and give you access to more monsters to fight for even more experience.
So, for indirect skills, you want skills that help your army in combat, skills that get you into combat faster and skills that keep your army size larger, either through increased production or through avoiding combat losses.
I've compiled a short list of the level 1 skills that accomplish the above. I did not include level 2 skills, though you could, depending upon your definition of early in game terms. However, most of the skills I have listed have level 2 upgrades, so obviously if the level 1 skill is a good choice, so is the level 2 upgrade.
I did not include any magic skills or Warcries in the above list, because they all help in combat, depending upon the faction you are using and the specific tactical battle plan you use. I think that any of the four Level 1 Warcries are effective in early battles and help keep your army intact, as well as the classic use of Slow and Haste to control which stacks attack first.
Finally, don't forget about strategic ways to ensure your main hero gets a lot of experience fast. For example, it never hurts to obtain a secondary hero as soon as possible. Your main hero can concentrate on just battles for the experience, while your secondary hero follows behind and grabs all the resources, artifacts and buildings opened up by the main hero, at least until you can give your main hero the Snatch ability, which allows her to pick up resources without expending any movement.
As far as I know, there is only one non-artifact option: "Enlightenment", under the "Might" affinity tree. It increases all experience you earn by a constant %.
It is in the first tier, so its available at level 1, even to magic affinity heroes.
There is also a Bronze Tier Dynasty Trait that increases experience gains for the hero.