Not sure if these will exactly line up with the sort of complexity you’re finding and enjoying in WoW (BTW I really like that aspect as well), but when I though of “detailed games”, here’s what I came up with…
Fallout 1 and 2, both for the PC, are in my opinion the pinnacles of western-style, turn-based RPGs. They have a great stats system, a bunch of unique and useful skills, a really cool concept of perks (basically specialized abilities that you get as you level up), “traits” (a lot like perks, but you only get them at character creation), and so on. I can’t say enough good things about these games. Fallout 3 is pretty good too, but I’d play them in order.
If you’re into SRPGs (games in the style of, for example, Final Fantasy Tactics), check out the Disgaea series for PS2, PS3, DS, and/or PSP. The hallmark of these games is their sometimes-ridiculous affinity for powerleveling and number-raising. For example, in Disgaea each of your characters can reach level 9999 (and this is game where level ~100 is more than enough to defeat the normal end boss)…and then you can return that character back to level 1 again and reach level 9999 in a different class, and so on. Every single item in the game has a randomized dungeon of up to 100 floors contained within the item itself that you can battle through in order to level up the item (yeah, you level up items as well). Oh yeah, and items also have little monsters living inside them that increase the item’s stats; by entering the items and conquering these guys you can move them around and customize your items to your liking. There are tons of classes, both human and monster, with multiple “ranks” of each class. In addition to the main story levels, there are lots of bonus levels that require levels in the thousands to stand a chance. There are 7 or8 weapon types which your characters can gain levels in, learning various skills along the way which of course can level up (basically everything in these games has a level or a number associated with it). These games are powerlevelers’ dreams, and they’re pretty damn funny as well.
One genre of games where a high level of complexity and detail is celebrated is Roguelikes. Though they’re not for everyone (the ASCII graphics and die-once-and-you’re-dead, no continuing aspect are offputting to some). Some do have rudimentary graphics available. Since death is permanent, you end up thinking long and hard about every skill point, what gear to wear, which spells to learn, which weapons to enchant, which god to pray to, which animal’s corpse to preserve and eat later (yes, really). My favorites are TOME, Nethack, and ADOM.
Recent Final Fantasy games aren’t particularly detailed or complex the same way WoW is, but I’d still say that FFX is one of the very best console RPGs of all time, so I’d check it out if you haven’t (I thought FFXII was pretty bad, personally, but many liked it, and the combat system is more MMO-like).