Spellslinger will have some ideas on this, although it has its own classes.
My take:
Setting: A newly opening frontier (open for whatever reason you want, the defeat of an ancient evil necromancer, improved modes of transportation, etc.) being settled after a war. The war sets up a situation similar to the wild west, in which people with the training that only war brings and the upheval in lives that only war brings move to the frontier. This gives you a reason to have adventurers with training beyond that of the ordinary person. In this frontier resources are discovered - mines would be the obvious choice but in a DnD wordl it can just as easilly be ruins of a past civilization.
Mounts: Keep horses, it will be easier on you in the long run and it will be one less setting detail for your players to keep up with. Perhaps there are wild magical horses that are highly sought prizes. Herd animals, on the other hand, might be different with a little more variety.
Natives: Gnolls, Minotaur, Lizardfolk, orcs, or goblinoids all are possibilities. Depends partly on what you want the "civilized" lands to be like. Any race you want to leave out of there you can add in here.
Guns: Magelocks. A handheld clockwork device in which a crystal is placed. These crystals are charged with magical energy. A small hammer stikes the crystal when the trigger is pulled, discharging the energy. Requires a ranged touch attack to hit. Damage is 1d6x spell level expended to charge the crystal. A full round action is required to change crystals, rapid reload drops it to a move action. A feat tree allows a caster to charge it without removing the crystal, first as a move action then as a free action around the time they can cast 5th level spells. A natural "1" cracks the crystal and it cannot be recharged. A confirmed critical failure (two "1"s in a row) causes it to discharge in the weapon, ruining it and damaging the weilder. Another feat allows spontaneous arcane casters who can aquire a familiar to bond with the magelock instead. Typically these weapons are only used by spell casters (allowing them to focus spells known on more utilitarian spells), creating sorcereous "Shooters" as the most notorious gunfighters. Most other people would use crossbows, or if you want to add that element, regular guns.
Other Ideas: Paladins as Imperial Marshalls. Bards as gentleman gamblers. Rogues as local sheriffs as well as notorious outlaws. Warmages and Sorcerers who foughts in the hardest combats in the war, now mustered out and regretting the horrors they caused in the war, Wizards few and far between out in the wilds but a few as mad inventors shunned back "east", Asian classes brought out to build the new frontier, Barbarians,Druids, and Scouts only in the "savage" races.