As a relative newcomer to the 4X genre, I was surprised by the length of time that it takes to get set up and out of your first city, with some decent units in your army, in this game. In the two games I've played so far, it's taken me until about 1420 to get off my starting island and exploring with something other than a magic spirit, and a bit longer to get units good enough to start taking defended lairs and nodes. Is this normal for the game, or am I missing something?
Also, I know that in the Civilization series, the game ends on a certain year, causing you to lose by default. Is the same true of Master of Magic, or do you have all the time you need?

yeah, I agree that 4X games tend to have a slow start. Though in MoM, some of that depends on the race and magic you choose.
What races and magic do you play?
Nature has a pretty slow start while Chaos is really quick, since Hell hounds a, re a spell that you get from the start and they're very effective for their price in the early games.
The Races of Myrror tend to have a slow start as well since the neutral cities are tougher as well as the nodes (but the prize is sweeter (I got a Sky Drake spell from a Myrror Node) and 3/5 myrror Races can live without nodes for a while since they produce they're own magic.)
A few quick starting Races are Gnolls (who suck if you don't work quickly in the early game.) Halflings (with the great Slingers and extra food and have the best relations with conquered cities)

My last two games were with high elves and high men, both (iirc) with Tlatoc, the prebuilt wizard with warlord. Shortly after my last post, though, I started a game with halflings and Lo Pan. Holy cow did I take off running with my slingers! I can definitely see how racial unique abilities can make a huge difference, which is a stark contrast to the few games of Civ 3 I've played, where the uniques make little difference. And yes, getting Sky Drakes from Myrror nodes is awesome.
Any word on whether or not there's a time limit in MoM, though?

I don't think there's a hard limit, though if you leave the AI alone long enough, They'll Learn the Spell of mastery and cast it, making you lose the game, you can do the same to win. I came close by almost learning it but I killed the last guy before finishing research.