Right. So I did this by thinking of characters in novels that I find fascinating, and then deciding on what makes them so. There is therefore no more objectivity here than usual.
Also, this should be obvious, but just in case: This is not about making characters likeable, which is another rant. This is just about what I think holds the reader’s attention.

1) Choose a quality that you find fascinating and show it.

This therefore moves the author away from doing nothing but telling me all about the beauty of the characters. Yay.
It also should prevent the problem that shows up when people decide to declare that their character has “intelligent green eyes” and then have the character act like an idiot. Intelligence, courage, ambition, wit, skill, endurance, patience, and so on have to be shown, not told. One sentence on her intelligence does not stack up against 100 pages of the character being an airhead.
So! Show me the character caught flatfooted, without any backup plan to get out of being caught with her hand in my lady’s jewel-box, and improvising her way out of the situation with a clever lie. Show her coming up with a battle plan that will keep the enemy army from getting inside the castle. Show her figuring out the solution to a mystery that has baffled generations—though you have to make the mystery really hard in that case, or it looks like the character solved it by chance. All of these are cool scenes to write, all of them work to demonstrate that, yes, this character is smart, and all of them will insure that stupid phrases like “intelligent green eyes” never show up again.
Do qualities by themselves make the character fascinating? No. I’ve read intelligent people I wanted to slap because they were pompous about their brains or fit too well into the “absent-minded professor” mode. But it helps when the author herself finds the quality fascinating and shows it off to good effect. Inspiring that kind of emotional bond in your audience will be easier if you share it.

2) Hurl the unexpected at the character, and then have them do the unexpected.

This is fascinating for the author, too, because he has to build the character’s personality like a puzzle-box or a plot mystery. There have to be clues that a character who seems fragile really does have what it takes to survive the coming storm, or a character who scoffs at everything and lazes around might care about his friend if convinced that friend was truly in danger. The narrative and the author and the character himself can insist on one interpretation, and the reader might faithfully follow that interpretation as far as it goes. But when the crisis comes and the character manages to do something unexpected and wonderful, the reader can remember the clues, respect the author for not appearing to pull this transformation out of thin air, and then get even more interested, because, hey, this is someone who has layers.
I actually have two examples for this, one fantasy and one non-fantasy. The first concerns Aunt Kade, the aunt (duh) of the princess Inosolan in Dave Duncan’s “A Man of His Word” quartet. Kade is the archetypal older woman who wants her niece to wear pretty clothes, learn her manners, take tea with the ladies, and marry the right man for her kingdom’s sake. Throughout the first book, Magic Casement, though she’s amusing and firm when she needs to be, I didn’t think of her as much more than a wall for Inos to practice her rebellion on. (That’s actually a compliment; Duncan is the one author I can think of who has managed to make me like his rebellious princess character).
Then the second, third, and fourth books show up, and Kade changes with them. Her firmness stands her in good stead in cases where Inos, unused to the challenges of diplomacy and politics, might crumple. And she has a sense of humor that grounds the series when it would otherwise take off into high-falutin’ fantasy. I’m still quite fond of her, and much fonder of her now in Casement than I was on first reading. All her qualities are there, some—like her familiarity with court manners—in plain sight, but Duncan takes his time developing them, and uses them in unexpected ways.
The non-fantasy example is Robert Audley of Lady Audley’s Secret by Mary Elizabeth Braddon, which is a Victorian novel of the type called “sensationalist fiction.” This was the popular literature of its day, because respectable people, of course, probably didn’t read novels at all, and certainly weren’t going to read the type of thing that has thunderstorms and secret passages and murder most foul in it. Robert is an extremely lazy man, something the omniscient narrator as well as he himself is happy to tell you—and then one of his friends gets in trouble. He doesn’t like it, he keeps displaying his reluctance to engage with the trouble even as he does it, but he manages, and displays an equally fascinating mixture of true change and rising to the occasion. Though the character development is probably clumsy in most modern terms, it has a lot to recommend it, and if you want to read it, it is online here. And, come on, it’s dedicated to Sir Edward Bulwer Lytton “in grateful acknowledgment of literary advice,” though, thankfully, much better-written than anything he managed. You know you want to read it. /pluggity-plug

3) Show them acting in perfect accordance with cultural mores that might be strange to a reader.

This one works with villains, too, since villains tend to be the more alien characters in many fantasy novels. I am firmly of the opinion that an author can make me understand why someone is doing something, make me feel empathy, and yet leave me rooting for the villain to die. So it works.
Admittedly, the best fascinations are those that intrigue the reader at first, then sink into her blood and become so much a part of the world she’s reading that she doesn’t notice them. I blinked quite a bit when I first read The Phoenix Guards, because Brust’s Dragaerans are killing each other left and right, and no one seems to feel much sorrow at those deaths, at least if they’re enemy deaths. Yet I excused that as being part of the Dumas pastiche, and kept reading. By the time I got to Five Hundred Years After, Dragaerans would not have been Dragaerans if they didn’t kill people left and right and not feel much sorrow at enemy deaths. They’re non-human, too, so that adds to the sense of alienness. And they still feel sorrow at the deaths of friends, so it isn’t impossible to empathize with them.
This is a delicate, dangerous game to play, probably because it might not seem all that delicate on the surface; an author can crudely remind the reader over and over of how harsh or alien this culture is, just by introducing that one (usually inexplicable) character with modern Western morals who stands in the middle of the carnage or sex or strange religious ritual and is sickened. But a viewpoint character who’s only following his conscience is a better bet. The author doesn’t need to apologize then. She can channel the strangeness through the character and the narration. This may lose her some readers, but the ones who stay may contract a bad case of fascination.

4) Characterize in ways other than through words or interior monologue.

I’m used to fantasy characters who have long conversations about their feelings—usually towards the end of the book, after denying those feelings quite vehemently in the previous few hundred—and then think about those feelings. Or they spend pages being introspective. Or they note that their behavior is different from what it used to be, and wonder if that’s a sign of change. When that works, it produces complex, fascinating people. When it doesn’t work, it is tedium.
It can be tedium even when the author is good at introspection and conversations about feelings, though, if that’s all he ever does. If the character has no gestures, facial expressions, sudden physical reactions to events, enigmatic visions, flashes of insight, or impulsive actions, then he’s too transparent. No reaction is complete without a tacked-on explanation. There are no shadows in his soul.
Though I have some criticisms about The Edged City, the book I just finished (and will be posting a review of tomorrow), I deeply appreciated that one character, Beth, is left mostly enigmatic. We see what she does. We see the art she makes. We see the reactions she causes in the people around her. We get thoughts on her from the “hero,” Gwynn, and on his relationship with her. But Gwynn isn’t that introspective, and usually winds up shrugging and admitting that several things about her might be true, and then not thinking about it again for pages. That makes what ultimately happens to Beth much more satisfying than it would have been if Bishop had tacked up every bit of her in photographs wrapped up inside transparencies surrounded by newspapers with screaming headlines.
“Fascinating” can mean mysterious in the sense of several possible explanations, rather than nothing to grasp hold of. Try other methods of characterization and see what happens.

5) Stir in some ordinariness.

One of the things I find fascinating about fantasy as a genre, though not always in a good sense, is how often it builds up a façade of ordinariness and then tears it down. The peasant hero is not really a peasant hero, but the long-lost royal heir. The heroine of the urban fantasy is hired to reupholster the chairs in the eccentric old man’s house, and it turns out he really hired her because his windows start glowing when she walks by. The bard makes normal music until he gets in trouble, at which point he’s a spellsinger. The king has a hunting accident in the most obvious of ways, but then it turns out he was murdered. (There aren’t that many ordinary deaths, especially of key figures, in fantasy. There cannot be! It is impossible!)
Yet while these are, if done right, cool and surprising and helpful to the plot, they lose the original fascination they had, that ordinariness. “Everyday” turns into a synonym for “humdrum.” The author apparently forgets that it may also mean “homey” and “comfortable.”
One thing I love about George R. R. Martin’s series, along with the brutality and the grayness and the character transformation and the growing magic and the beauty and the pageantry and the half a hundred other things that I can’t list for you because then this rant would turn into a Martin screed, is how his characters, grand and mighty as they are, do have that ordinariness at the heart of them. Jon Snow gets shown as Someone of Importance right away. There are at least three different theories current in the series about his parentage, and Martin apparently plans to introduce a fourth. He has an albino direwolf, while his brothers and sisters have ones of more ordinary colors, and he’s quite good with a sword in comparison to the other boys among whom he finds himself, and he stands up to enemies who should overpower him, and so on. But at the same time, he’s extremely unromantic—here’s one fantasy teenager who doesn’t take his introduction to fantastic creatures with grace, but with unease—and often suspects that he has no idea what the hell he’s doing. He’s also extremely oversensitive about being a bastard, and other people frequently mock him for it. Growing some good qualities doesn’t miraculously transform his relationships with everyone else into ones of grace and glory. He has a long way to go as far as that’s concerned.
Probably an even better example is Daenerys Targaryen, Dany’s an exiled princess (check), has an almost inhuman beauty (check), is abused by her only surviving family (check), is being forced into an arranged marriage with a much older man when we meet her (check), goes through blood and pain (check), and is obviously going to achieve Great Things (check). But she also suffers pain from riding, struggles to learn her new husband’s language, has to go through with duties that she finds disgusting and distasteful, gets dirty, gets tired, likes hot baths, and realizes that her dreams about “home,” which she’s never really known, are vague and wistful. There’s no check for that. Dany’s not just another princess, because Martin doesn’t exaggerate every facet of her life. Nor does he tie everything back to her being royal and beautiful and destined. He gives her what makes her her, small as well as large.
And that appears to be quite enough chatter on the subject.