Oh man, I love Majesty. I'll be honest, though, I'm cheating garbage and always used, like, ALL the cheats.
My favorite thing to do was split up the map into 9 segments - y'know, middle, north, north-west, south-east, etc - and build a tiny little town way in the corners. Usually I'd fill it with all of the guilds for one kind of adventurer, and related buildings. Like, there'd be the shady rogue town, the magical town with the Bazaar... and then there'd be like, the holy town, with like one of each temple in it (cheats!). Also guardhouses and trading posts for everybody.
I guess I just liked the idea of having lots of little townships and divisions, I guess, sending trade caravans to the big 'capitol city' or whatever. Uh, I also rushed the Mausoleum, because it made me sad whenever my heroes got ded and I wanted to revive them.
Gnomes are the best, also.
Alsoalso, this reminds me: Wasn't there like, one of those online, kinda-ghetto, website-based RPGs based on Majesty? I remember it having slightly altered portraits, so you could choose what class and what gender your character was, instead all wizards always being guys, for example.