I got the game to run perfectly in Cross Over Games on OSX, but it took some experimenting.
First you have to create a Win2000 bottle, because there were some issues with the .net framework installing that didn't work under an XP one.
After I created the Win2000 bottle I installed Visual C++ 2005 Redistributable, Visual C++ 2008 Redistributable, Visual C++ 6.0 Redistributable, and DirectX (Modern), all from the supported installations dialog within Cross Over. I installed things in the above order but I don't know if all of it is necessary (or has to be done in that order), that's just what got it working for me.
After that I installed Steam through Cross Over, downloaded Majesty 2 through Steam, and launched it. It launched correctly without any issues and I played it for several hours. The only bug I came across was that I couldn't type periods into the GameSpy login dialog, so internet matchmaking didn't work since I couldn't type the .com into my email address for my account login. Other than that everything worked perfectly.
I tried the above steps with the Direct2Drive digital version as well but this failed because it was unable to authenticate the DRM for some strange reason. That failure happened whether on an XP bottle or Win2000 one. But the Steam one was perfectly playable and got great FPS on my 13'' Unibody MacBook Pro.