Another that I just thought of is The Sons of Katie Elder. It has some cheesy moments, but I’ve always liked it.
You really can’t go wrong with an old John Wayne western. 
A double feature:
Yojimbo
For a Fistful of Dollars
Another double feature:
The Seven Samurai
The Magnificent Seven
These are the Japanese originals/American remakes.
Kurosawa’s cinematography is nothing short of astonishing. You may re-evaluate your preference for modern film makers.
And is, of course, a spiritual successor to the Leone movies.
I always thought of Pale Rider as the spiritual successor to Shane.
Yeah, but Shane has a name. 
Check out The Quiet Man and In Harm’s Way. Wayne was definitely capable of acting when the part required it.
Patricia Neal!
A terrific film, massively underrated.
On a different note, I always recommend Jim Jarmusch’s Dead Man (1995) with Johnny Depp for a great modern reinvention of the Western.
Three Godfathers.
Loved Dead Man. But then, I’m a Jarmusch fan. So many good scenes. Drawing on Robert Mitchum’s portrait, Lance Henriksen’s dinner, ‘Sally’…
My ex-fiancée hated it. She said she watched the whole thing just to see if the guitarist (Neil Young) would be shot at the end. But when we talked about it, she admitted the movie itself was good. She just didn’t like the music.
I have to admit that The Shootist is my absolute favorite John Wayne movie, and western movie. I am not a big fan of John Wayne, but something really resonates with me in the movie.
Nobody mentioned The Cheyenne Social Club? That is my second favorite cowboy movie =)
My own favourite is Sergeant Rutledge. Dad’s was High Noon. Middlebro almost had a heart attack when he discovered that his bride had never watched Stagecoach; this was particularly surprising given her father’s love of Westerns - until you realized that watching anything with him in the room was closer to torture than pleasure.
Just thought of another: Calamity Jane.
Wow, thanks for all the replies fellas. Just finished A Fistful of Dollars, watching For a Few Dollars More next. Got to say that I’ve always prefered Clint Eastwood to John Wayne as an actor, but might try The Shootist next. For connoisseurs, how’s that pronounced? I’ve heard from purists that it should be ‘shot-ist’, rather than ‘shoot-ist’.
Well, I figured that if I couldn’t get into the seminal work of the genre my nascent interest might be rather stillborn, fortunately it was brilliant stuff, so time to delve a bit deeper I think.
Deadwood, Deadwood, and, of course, Deadwood.
I’d suggest The Quick And The Dead. It’s relatively recent, and not what I would call a “real” western, in fact the entire film is pretty much an excuse for Gene Hackman to eat the living shit out of the scenery while shooting at people, but it’s highly entertaining if you’re into that :). Oh, there’s also DiCaprio, Sharon Stone and Russell Crowe in it. But it really is Hackman’s show.
As for more classic westerns, well, Rio Bravo’s cool even if you’re not really into John Wayne (but then, I’m a Dean Martin fan) and of course Once Upon a Time in the West is nothing short of brilliant.
Dana isn’t there for her acting… 
There are different types of westerns including comedy westerns, musical westerns, and drama westerns and actions westerns.
I don’t recall her being nekkid. 
I don’t like westerns in general (although, like the OP, it may be a mix of unfamiliarity with perhaps a dose of unfair preconceptions thrown in), but this film is nothing short of brilliant. The opening scene of this movie is my favorite cinematic opening scene, and the movie itself ranks somewhere in my personal Top 20. Do not miss this movie.