Basically, you will want to reach an average of one province per turn (more if possible), but since you cannot take two provinces on the first turn (on Independents 6 at least), that means taking a few more provinces on the way.
As soon as possible, the capital should be recruiting one mage per turn, with other provinces recruiting the mundane commanders needed for leadership. Most nations have access to a cheap mage for research: the Daughter of Avalon for Man is a prime example. Some nations have access to mages cheap to recruit, and others cheap to maintain: for example, Marignon has both the Initiate and the Inquisitor, and they give the same amount of research. However, the Initiate is more expensive to maintain, since he is not holy, while the Inquisitor will cost you more to recruit. In those cases, you should see if you would rather have a couple of priests just in case (undead invasion, Pretender being killed...), or if you cannot afford more than those 65 gold coins for the Initiate. If you are wealthy, you can go the Witch Hunter way, for a faster research, or even the Grand Master... but recruiting one Grand Master a turn may be difficult.
Still, you should not expect to be able to research and search sites at the same time if you need some of your mages for expansion. The low-level mages (Inquisitor and Initiate) are good for research though, so those will likely stay at home and not do anything else. A couple of Grand Masters should handle your magic searching, along with your Pretender, if needed. Site searching is likely less important than expansion however, unless you are considering selling a province: in this case, either you search for sites to see if you should really sell the province, or you don't search it and let your neighbour do the job.
I would rather search for sites in this case though, as giving them a -50% blood site would *hurt*.