Heya again,
I'm not sure it would be possible to do a 'quest' type of thing with Civ3 under it's current limitations in editing. However you could build a mondo middle earth war zone.
(by the way several years ago someone did a great quest with frodo and middle earth, I thought it was for civ 2, whoever that was should be get bee--- err cokes bought for 'em)
If you took a pre-ring war idea, maybe even going into the wars of mirkwood and the necromancer of um..gosh the name escapes me, (I hang my hobbit head in shame).
A couple of ideas for the map,
Use Gondor as the key to the halves of the maps. Meaning draw an ocean line (as in the previous post) down the center of the map, and only have one square join both halves. Put the starting location for one of the factions right on this square (then the AI will build there 1st turn) so whoever controls gondor can cross the "river" without the expense of boats, problems with loading unloading ect.
On the eastern side build Mordor maybe with a few lesser nations (controlled through the kind of territory you give them, making mordor rich in food/rivers/production squares and the lesser fiefdoms a little poorer, (like bonus grasslands with rivers vrs plains without.)
On the western side, build Lori..um, Lorie..gosh my speller is going on me, St. Nick must nicked it from me

, Galadriel's Digs as one nation, set in a high productive forest (change the food/production rates of forests in the editor) the shire as another, the dwarves as another etc etc.
With diplomacy I'm not sure there is a way to limit or force alliances, though if you want to apply a little alternative history to Tolkien (I know don't throw rocks it's just an idea) with the attitudes of the folks in Gondor them siding against the Lady of the Golden Wood isn't inconcievable.
Next idea is let the unit created during battle be great, not just an army builder/production hurrier, but give it enough pop in defense/attack to let it make a real difference, OR let it only hurry improvments then make HIGH cost special units...like the balrogs that were talked about, that do all sorts of nifty stuff from build armies to be able to shoot lightning bolts out their bums. make the cost so high that only the sacrifice of a 'winning battle unit' can build it, to limit them.
and lastly you get into the modern era, someone mentioned Grunts, but combine 'magic' with tech, (mostly visible in the unit animations looks.) so you get things like
High Elven Mech Archer, which shoots flaming thunderbolt-arrows that exlode in the animation on contact. A good artist could have a lot of fun with this, assuming they never wanted a job, wife, or social life.
I'm not sure the AI would use the special battle unit to build the expensive units though, they might waste them on wonders or something. In multiplayer it'd be kinda neat cuz then folks would be investing thier battle-ribbons in building gandalfs and ring wraiths.
Post script idea. Use barbarians, give them a great unit, make the odds even in the barbarian handicap system they installed with the patch, and then give barbarians a real nicely designed couple of units, like um, dragons. You could even make (if you were drawing the map by hand) one terrain type (like swamp or sumthin you don't wanna use elsewhere) HIGH in defense put the barbarian camps on these, making it harder to clear the pesky things out. whcih could backfire if the AI cleared out the camp, then built a city on the terrain type (I'm assuming the terrain bonuses transfer to a city too)
But it'd suck to be a little hobbit starting out your third city of Tookland and have three all-terrain dragons (equaling like modern armor) come flying in with throats blazing. Sucks, but in sorta neat way. Esp. if you were playing the dwarves.