Talislanta. It is now in its 5th edition, although I am a 4th edition loyalist. It's an incredible mashup of classic swords-and-sorcery with slightly hallucinogenic fantasy. Think The Dying Earth meets Swords Against Deviltry meets The Dark Crystal. It's probably slightly less complex than you were aiming for and it has a venerable history, but from the sounds of it, you are looking for something fresh, and Talislanta would feel fresh to anyone. Forget paladins and elves and holy avengers, and think Zandir duelists, four-armed, battle-mad Ahazu, and ice giants.
Warhammer FRP 2nd edition is, of course, awesome. It's one of those games that's great just to read, but it's also an easy game to pick up with a new group, and the combat system is just a beauty in action. The milieu is sort of The Lord of the Rings meets Stormbringer meets Lock, Stock, and Two Smoking Barrels.
I know you said no GURPS, but the new GURPS is very slick, and GURPS Banestorm is a very slick revision on their Yrth setting, which gives you an alternate world in which the Crusades are still going on against a backdrop of mythological and alien races like elves, lizard folk, and octopus people.