Well that's the cool thing, it's not Maj'Eyal it's Middle Earth
I haven't played Tales of Maj'Eyal (ToME 4) either, just this old version which is set... uh, rather loosely... before The Hobbit. Though with Yeeks and half-ogres and other Angband things. The overworld map is a pretty faithful recreation. Most of the unique creatures and artifacts are from Middle Earth.
I particularly like the faith system. Instead of clerics basically just being wizards with a different list, every character can worship one of the gods (including Melkor). Even if you don't/can't put points in pray (there's a skill system based on class) you can still get significant benefits from having good standing. As a follower of Tulkas, my mindcrafter gets a significant boost in accuracy while praying. It costs piety, but Tulkas is easy to please- he likes it when evil things die, especially demons.
http://www.killerbunnies.org/angband/god-220.html#tulkasThe hardest and most interesting is definitely Yavanna, ha. She gets really upset if you kill animals... Animals which are generally trying to kill you, like any *band. But she likes it if you charm them instead, and she offers a cheaper animal-only charm spell to the pious. Not so bad... except you're held responsible if any trees on the map die :/ In exchange for all this headache, you can terraform the vilest of places with beautiful grass, and regenerate rapidly while standing on it.
Tulkas is so much simpler though, heh. Almost as simple as Eru... He likes you just for existing, and his spells let you experience the music of creation (divination/detection, mostly).
Manwe might be the best because his devout followers get constant speed boosts, flight, and can temporarily turn into maia-avatars or something. Madness.