I met him in Whiterun. Then I proceed in rejecting his offer base on suspicion. Then I got curious after x amount of hour of gaming and wiki him. My suspicion was well place.
Its random. He can be found in any pub in the land if your level is high enough. Sofar on 4 characters ive met him in Ivastead, Whiterun, Riften, and Solitude.
i met him in Riften around level 20. im now level 45 and...
Spoiler
last night i was wondering the countryside and some kaijiit came up to me telling me he cleared some dungeon that i bet him he wouldnt clear out and now i have to pay up on my bet. i followed the dialog and apparently i met him the night i blacked out and bet him that he wouldnt clear a bandit hideout.
it was honestly the BEST random encounter ive had in the game yet. mostly cause i completely forgot about that mission until i ran into him randomly walking through the country side. This game is so amazing!!
I met him in Windhelm. Since I got the Oblivion Walker achievement with my very first character, I haven't even glanced at him with this character. lol
Bannered Mare in Whiterun and was I ever surprised. I never did the quest with him in Oblivion so it was quite the experience in Skyrim. I don't do all the Daedric quests but I'll do this one again...the reward is huge.
Markarth for you? I guess you didn't save 20 gold septims on a carriage ride then.
Funny you say that, even though I did the quest before hand (Unknowingly) I automatically thought I had unlocked the fast travel but you need to walk to the gates, I fast travelled away before that so had to walk my way back later =(