I second the suggestion for checking out Deadlands.
Some other things to consider:
1) Harry Turtledove's
Darkness series, a retelling of WW2 but in a fantasy world, featured a different kind of staff that fired a beam of eldrich energy and was rechargeable. While it was usually recharged by wizards, it could also be recharged with life energy...
IOW, guns.
In D&D, you could consider them a magic rod/staff/wand (DM's campaign design decision) that only fires something akin to a warlock's eldrich blast, rechargeable with spell levels or warlock's blasts or some such. Recharging it necromantically would require a Feat.
2) One of D&D's designer's PCs (Rary? Whomever, I believe he was in the 1Ed Rogues Gallery product) from the days of 1Ed was dressed in Western garb and fired Magic Missiles from a pair of six-guns. Without the guns, he couldn't fire the MM, and they couldn't fire real bullets, either.
Again, its some kind of gun. As I recall, the mechanic of this PC made it function more like a Warlock's eldrich blasts, but with the limitation that the PC have a certain material component (the "shootin' irons).
This could be handled with a modified "Innate Spell" type feat that, because you have to have an "attuned magic item" to cast the spell, you don't have many level adjustments on the spell. Psionics or Incarnum would probably work as well.
3) For Native Americans, I'd sub the D&D equivalent of the Sky Elves of Elfquest. IOW, Giant-Eagle riding masters of the plains. OTOH, I have also cast Minotaurs in that role in a 2Ed campaign (for the record, "Indians" with giant-sized bows are MEAN)- though they used chariots, not actual steeds.
You could also have various RW nationalities reflected by the plethora of sentient races available in 3.5, and sprinkle these new nationalities throughout your Arcane West.
For example:
The stereotypical Dwarves seem Teutonic/Germanic, though the Drow were also inspired by teutonic legends. You could give Germany to the Dwarves and places like Finland and Iceland to the Drow. They'd even still be the "Dark" elves, living in inhospitable climates with the long days and nights found in/near the arctic circle. In the Americas, they'd gravitate towards the more northern climes.
The post-Ottoman Empire arabs could be represented by Orcs- fierce warriors with a great culture in flux, spearheading advances in science and philosophy while sheltering pirates out of Tripoli. Half-Orcs would be the result of the Ottoman expansion into Europe, resulting in them being the majority of the Balkans, many of whom were among the first European settlers of America.
Gnomes could represent the Asian nationalities- assuming you don't use OA or similar products- and, like in the RW, would emigrate to the Americas to work on the railroads and the gold mines of California.
And so forth...
4) Alternative mounts: other than the giant eagles mentioned above, consider:
Kurt Giambastiani's "Fallen Coud Saga" alt version of the Wild West had no oddball races, but the Native Americans rode some kind of velociraptors.
http://www.sff.net/people/giambastiani/Novels.htm
Similarly, and slightly less fantastical, you could have them ride large flightless birds. Moas and other "terror birds" were definitely large enough to serve as steeds- people can ride the much smaller Ostrich in races- some American species survived as recently as 15K years ago, and one (the Elephant Bird) survived on Madagascar up until 300 years ago. A little twist, and instead of killing them off, the Native Americans domesticate them. They are powerful animals, very fast of foot, and with fearsome natural weapons. The Axe-Beak is one D&D take on them, there may be others.
http://www.newanimal.org/moas.htm
The aforementioned Turtledove books also features fire-breathing dragons of animal intelligence and camel-like disposition that serve as the basis of the air corps for his world's air forces. However, to keep their fires burning, they must be fed coal and cinnabar, so mines of those resources are of great strategic importance.
You might want to check out comic-book characters like Ka-Zar and Turok.
Other good sources would be the 2 TV series
Wild, Wild West and
The Adventures of Briscoe County, Jr., and to a slightly lesser extent,
Kung Fu.
I also liked the suggestion of clockwork critters as steeds. Perhaps the Native Americans use Terror Birds and the invading Europeans use Clockwork Horses...
Heck, you could even have Whaleriders or
Dune-like Worm riders- goodness knows there are plenty of worms in D&D.