Oh man, I *love* FFH2. I hardly ever play vanilla Civ4 anymore, just FFH2.
I've played with every single civ, but so far I've only beaten it with a handful (Bannor, Grigori, Elohim, Ljosalfar and Balseraph, I think)
Sheaim can be very fun, because you wind up with an army of random assorted monsters once those summoning gates get built. And as the world goes to Hell, you get stronger.
My favorites these days are the Amurites (trying to go for a Tower of Mastery win), Lanun (paired with Octopus Overlords and a water-rich map, you can be quite powerful), Ljosalfar (cover the world in forest and influence, and then use your World Spell to summon seventeen metric f**ktons of Treants to finish off the remaining enemies), and Clan of Embers on a "Terra" map (where everbody starts in the "Old World" and races to discover and settle the "New World" full of barbarians. You're at a research disadvantage, but if you can level up Rantine bigtime and put him on a boat to the New World, he can go from city to city converting them and giving you an empire out of nothing)
The only ones that are somewhat boring are the Sidar (although they got a bit more interesting in the final update or two, with some of their "divided soul" abilities), the Malakim (there's just not enough desert for their bonuses to be of use, although with the addition of the Overcouncil, they suddenly became a lot more interesting in terms of going for a diplo victory), the Doviello, and the Hippus. Even those, I think could be fun if I just figured out how to use them properly.
But my vote is going to be for the Khazad. Why? Because THIS IS DWARF FORTRESS!
Plus, you have little to worry about in the way of magic, and religion really isn't their thing (Yes, they would do well to adopt the Runes, but the Luchuirp are more geared for being religious dwarves). Khazad strategy is straightforward: Build a few cities with lots of hills and/or trade resources around them, and mine the shit out of them. Build up defenses, make money hand over fist, stay out of wars as much as possible, and build up doomstacks. Once you've got cannons and some assorted higher-level units, open your gates and unleash the dwarven war machine on anyone nearby.