I really like the various "japanese" nations - EA Yomi, MA Shinuyama, LA Jomon.
They're well done, rich in strategies, have nice special spells and creatures, and are rather powerful (at least EA/MA, I'm less sure for LA).
Didn't try everything at all, and should try R'lyeh for sure !
