So I just spent the better part of a week grinding to 81, and have even capped all skills as well, but have yet to see The Ebony Warrior or have the quest flag in my log.

I have completed all major quest lines as well as the majority of all minor side quests. I started and finished Dragonborn before reaching 81 though.

So now I'm traveling between all the holds just HOPING he will show up, but he still hasn't.

Should I try the island? Or am I just missing some key part of the quest requirements? I really want to start this quest, any and all help would be greatly appreciated.

Just keep fast traveling to towns. You'll know it when you're forced into dialogue and **** your pants that you found him.

How long does it normally take though?

It's random, but it took me quite some time, as well. Just keep fast traveling to major cities and stay for a tiny bit. He'll activate eventually. For me, he showed up in Windhelm.

I'll keep trying. But I can't help but feel morale is slipping amongst the many folks claiming that he won't spawn if you already started/finished Dragonborn.

I got him right away on two different characters. Once in Riften and once in whiterun. No rush to do the quests though since there's nothing great about the reward.

He is really tall though.

I could honestly give a [censored] less about a reward, I crave the challenge. I've never fought a character that gave me any trouble, even on master, and I'm eager to face a worthy adversary.

He's always showed up in Whiterun for me (five level 81's, always appears in Whiterun), have not encountered him anywhere else though.

You can make a skeever challenging if you want. Fight it with no armor, no magic, no potions and only using your fists. Odds are your using some things to help you so your denying yourself challenges.

Take heart given the responses here: http://www.gamesas.com/topic/1429026-ebony-warrior-met-when/

I found him in Riften after quite a while. He certainly is challenging, I was pleased with the fight, but ultimately he fell to my blade.

I still think I accidentally killed him.

The only time I've seen an ebony warrior guy, was when I first went to whiterun to start this DLC. There were some
cultists, so I just assumed this "ebony warrior" guy, all in black, was with them.

I killed them all, including him. He seemed to be no big deal.

Was that him in the quest giving form and I screwed it up? He was no way near as hard as the ebony warrior
people talk about, nor did he have all of the listed gear.

I wondered if it was a fluke, so I've been fast traveling to old world towns now and again, but never see him again.

random ocurance
may have to be very high level also
i met him my first fast travel after installing dg at lvl 81

I found him when I fasttraveled to windhelm after completing all the dragonborn quests, there might be some confusion because I know some random encounter spawns a mercenary in full ebony along the roads and that had me fooled a couple times

Fast travel to Whiterun, he is usually standing right there.

*

Does he appear in Solstheim

What is the hype about this Ebony Warrior about? Can I get more details about this? I have one of my characters that is level 81.

He's essentially the most powerful enemy in the game, though calling him an enemy seems in bad taste due to the fact that he challenges you to honorable combat atop a snowy mountaintop.
He's allegedly leveled to 80-81 just like your player character, I believe he has the Heavy armor perk 'Reflect Blows' which means hitting him can damage you, sometimes to the point where you will kill yourself by hitting him. Overall he's just a really fun, and really challenging fight. Something really worth the time and effort of a powerful character, unlike most other monotonous tasks given to the player over and over again that are boring and droll. Beating this NPC is something you can actually be proud of and feel accomplished over.