The first thing you must do is to build a unit with all of your strongest people. There are no limitations to this unit except that it has to have one of those eagle dudes so it can move really fast. At the beginning of each level, have all of your units except for the unit you just made take the quickest route directly to the boss's castle. Forget about liberating cities and temples. The unit you just built you should move to the boss's castle too, but it should take a different, longer route as it will be travelling faster.

The bad guys will be so occupied with your big army marching straight toward your castle that it will not notice one little unit wandering around the back. After you beat the level, go back and liberate all the towns you missed.