The Painted Man is really, really fantasy. There's not subtle about it - it throw you in the deep end with demons and warriors and whatnot. It is a cool, crazy world, but I'm not sure I'd recommend it as a "first" fantasy. It is pretty full-on.
Going back to Jdiddy, what does the reader like when they're reading normally? War stuff? (Abercrombie - and probably The Heroes or Best Served Cold) Mystery? (Scott Lynch's Lies of Locke Lamora or China Miéville's The City & The City) Historical fiction? (George RR Martin or Naomi Novik). Politics? (KJ Parker's Folding Knife). Horror or SF? (Well, loads of ways to go there...)
Even if they're interested in, I dunno... martial arts, food, Chinese culture, westerns, superheroes, ancient Rome, philosophy, etc... there's a fantasy book for everything!