I'd recommend LotoW first, too. But just to throw a few more into the pool, here are some other games/rulesets that you could look into:
Deadlands is a "wierd west" setting, I think of it primarily as a role-playing game, but you could probably make a skirmish game out of it.
G.A.S.L.I.G.H.T. is billed as a Victorian Sci Fi setting, but essentially it's pretty much a quick-play set of skirmish rules ("gaslight" stands for Glorious Adventures in Science Loosely Involving Generally Historical Times). There's an expansion called "Civil War by G.A.S.L.I.G.H.T." and you could easily play that ruleset for Old West skirmishes.