First up, books.
I've had a hard time finding Western-themed works that fit my definition of "high fantasy" (and the definition I'm using for Daughter of the Wildings): fantasy set in an entirely different world from our Earth, with no reference to the real world, involving magic as an important plot element and a struggle between good and evil. But there are a few that come close, and there's plenty of other stories that fit into the Western With A Twist theme out there; "Weird Western" is a big trend, as is western paranormal romance (my own definition of paranormal is set in our world and dealing with things like ghosts, demons, vampires, etc), western steampunk, western alternate history, and western science fiction. Here's a rundown of some books and a web comic I've found that fit the bill of Western With A Twist.
The Mick and Casey stories (Have Gun, Will Play; A Fist Full of Divas; The Curse of Scattershale Gulch, and two stories in the Waiter, There's a Clue In My Soup! collection), by Camille LaGuire. Young married gunslingers Mick and Casey McKee solve mysteries in the old west. Mick and Casey are great characters, the old west settings are beautifully conveyed. If you enjoy putting together the pieces of a mystery in a different setting, try these. Personally recommended. [Amazon]
Next Town Over, by Erin Mehlos. Follow the mysterious Vane Black as she pursues rogue sorcerer John Henry Hunter across a fictional world based on the Old West. Western high fantasy with a good dose of steampunk, an intriguing story, and really cool art. Personally recommended. Read for free or buy collected volumes for your tablet or in paper at http://www.nexttownover.net/. (I read them on my Kindle Fire.)
If you have any recommendations for books that are western with a twist that aren't listed here, please put them in the comments!
Part 2: Movies and TV
Part 3: Music