Oh my gosh. I can't even get anything going on the Introductory level!

It is always the same, I do my best to get a granary, marketplace, get some fighters, explore, etc. Then maybe build an additional city. At one point a had 3 slingers, 2 heroes (waited until they were level 3!!), and a swordsman. Tried to take a node, and got wiped by phantom warriors. Then I re-built my army, this time with 4 bowmen and 4 swordsmen in the front, the same phantom warriors killed me again. And I even had a training on them!

How in gods name do you get any nodes early in the game? And why when I use my boat and go look at the opponent does he have a city with all these nodes around him lit up like a Christmas tree?

Phantom warriors can be particularly tough thanks to their "illusion" ability, which lets them completely ignore a target's defense rating--thus, heroes will get butchered by them pretty quickly! Most low-level magical (summoned) creatures are a good match for them, as well as most node-guarding things you'll run into, though. Support spells can also make a big difference, if you're casting from the same school as the node.

Another thing I'd recommend is summoning magic spirits to serve as your early game scouts instead of waiting for ships--the mana cost is sort of steep at the beginning, but being able to explore the whole map right away is pretty helpful.

Definitely use magic spirits as scouts. And don't necessarily attack anything you come across! Pay attention to what the guards are, and then pick and choose the ones you think you can handle. Avoid any node or other location that has "many" guards, because that will likely mean 8-10 units or something. Some guards are pretty easy, however, so aim your army at those.

If you need to take out phantom warriors, try using some flying units or units with ranged attacks. If you have Nature magic, summon some sprites, who are both flying AND have a ranged attack. They'll make short work of phantom warriors, at least until they run out of ammo. Your regular troops, like swordsmen and pikemen, will be better against enemies without any special abilities, like zombies.

Slingers are great, but remember that they are less accurate at long range, and won't be very good against enemies with missile immunity. Still, I found that slingers made short work of most enemies, even at long range, once you build enough of them. With a few more units of slingers you should be able to take out phantom warriors before they can reach you. Don't charge them with your melee units though, since their illusion attack will make short work of your troops.

Also, don't forget about your spells! They're quite useful both in and out of combat. Which magic schools did you pick?