1. Almost positive it only affects troops trained after you build the building.

2. This is tricky and opinons probably vary. This is why I am big proponent of removing the XP split. You can send the hero out solo to grab goodie huts and scout, but I find two or three militia is usually enough to clear low-level mobs. I go cheap with them until everything is up and running full steam.

3. The magic tree is good for the spells, shard harvesting, and magical equipment. The magical equipment tends to give hard to get bonuses, the magical staffs are the best ranged attack in the game (ignore armor), and late in the tree the magic weapons are pretty good. These all cost crystal, so if you don't have access to it it is not a good idea to research deep in that area. You can look at the spells and see what you like in the tree, the two I find most useful are tireless march (best stack moves faster) and annointed by fire (gives an extra mage or primary mage fireball).  If you want to use shards at all you will need the first tech at the bottom, later on you can upgrade your mana income from shards to +2 and +3.

I generally head off in one direction with the main stack, and with about three militia and a hero I can comfortably clear most things that are immediately around the starting area. I don't try for anything other than bandits, mites, wolves, and maybe some lesser stacks of other things. With two militia and a hero, it is more the weaker stacks of that previous list. The clubbing ability kills those creatures pretty well, and the militia are tough enough to live through an attack or two of the survivors. It is slow going because the militia need to heal between battles, but I usually just do this to give the hero something to do until my empire building has reached a point where an adequate army can be built without taking 20-30 turns out of my only city's queue.