I haven't played WoW, so I'm not 100% sure what Talents even are (are they skills?), but the director of WoW said their talent system didn't work as well as they had hoped, and instead praised Call of Duty: MW2's system as superior (in some aspects). Note: The company that owns Call of Duty (Activision) merged with Blizzard to form Activision-Blizzard, shortly before he had said that, so he wasn't praising a competitor's game (which would carry even more weight in my mind).
One of my favorite games from my childhood is Quest 64. In Quest 64, when gain enough experience, you get a single point to put into your magic. You can put it into four different categories: Fire, Water, Earth, Wind. My family each chose a different element.
Two things were exciting about this system:
A) You can find skill points (called 'wisps') scattered around when exploring the world. Real skill points. That's pretty crazy, but very enjoyable. You find a wisp, click on it, and it's exactly identical in behavior as if you had just leveled up. Even catching a glimmer of a wisp was exhilerating.
B) You didn't know when a new skill would be unlocked. You'd gain a new skill for every 4 points you put in that element, but it might be three or five or even six points before you get a new skill. So after every point put in, we'd scramble through our sprawling non-linear skill menu checking if any new skill was unlocked, which built anticipation, like looking for an Easter egg. It was very pleasurable to finally see one in the menu!
C) Finally, you didn't know what that skill would be! Once a skill was unlocked, it'd just say it's name ("Water pillar" or "Hot steam"), and you'd have to actually use it in battle to learn what it did, and how to properly direct it at enemies (there was no targeting system).
(This was in the era where we barely had the internet, and while using GameFAQs on occasion, we tended to avoid spoilers).
D) This was my first RPG ever, so at the time we didn't know what 'experience' was. As far as we were concerned, we'd randomly get level ups when defeating enemies, which was another burst of exhilaration any time it occurred.
It took us awhile to realize that this sucker wasn't tracking the day/night cycle: :P
Even after knowing what it tracked, it was still exhilarating to level up, because the experience bar wasn't constantly visible on the HUD. To paraphrase Sean Connery in Finding Forester: "The key to a gamer's heart is an unexpected gift, at an unexpected time."
Another system I loved was Fable's. Fable discarded leveling up entirely, and instead let you accumulate experience, and use experience as a currency to (effectively) "purchase" new skills (in a skill tree), or purchase level ups for those skills.
Further, there were three separate skill trees: Dexterity based, Magic based, and Strength based (or something like that - it's been awhile). If you used mostly Strength-based experience against an enemy, it'd give you General experience (spent on whatever tree you wanted) as well as Strength experience (spent only on the Strength skill-tree). So there were three types of experience based on what types of skills you were actually using, plus a general experience spent however you wanted.
A third system I enjoyed was Paper Mario's (a Mario turn-based RPG).
It was broken into two system:
1) First, you gained experience from enemies and leveled up (like many RPGs), and upon each level up, gave you three choices: Increase your max HP, Increase your max MP, or Increase your max Badge points.
2) Badge points let you equip badges. Badges are skills - either usable or constant effect (so you can equip constant-effect skills that are continuously on at no MP cost). You find badges in the world through exploration and so on (some merchants sell a few of them). There's a fixed number of badges in the world, almost all of them unique, but a few have duplicates, and they can be stacked.
By having badges instead of skills, Paper Mario lets you continually reconfigure/reequip what 'skills' you have (similar to, say, Final Fantasy 7's material). Different badges take different number of badge points to equip, so you have to make choices based off of trade-offs ("I can have this really powerful attack, but it takes five badge points to equip! I only have 14 badge points, so that'd mean I probably wouldn't be able to equip my constant-effect health regen badge, or my badge that reveals hidden items as I'm exploring... Or the badge that lets me use two inventory items (necessary for healing) on one turn...")
[Edit:] Could you go into detail about how WoW's Talent system works, and what you enjoyed about it? I'd love to hear what parts of it made it so enjoyable to you!