You can get some initial ideas of looks you like by searching "Saltillo" among kitchen photos on Houzz.

Being born and raised in Arizona I absolutely love the Southwestern style design, and LOVE your Terra Cotta flooring!

I would suggest doing a Colonial Gold Granite for the countertops, and a 6x6 tumbled travertine backsplash laid on a diagonal would be beautiful! If you'd like to really play with the Southwestern influence, you can intermix a Spanish deco tile every 2' or so in the travertine backsplash (just for an extra fun pop!)

Some photos are below to show examples of the materials I've suggested.

One thing I love about Southwestern Tile is the intricate and bold designs you can find. I agree with Alexis' ideas and would also like to add, picking a tile pattern as a focal point behind the oven.

Something similar to these photos:

In this thread, too, I recommend gold paint for your cabinets, which would go well with the granite suggestion above. Not going to go find the photos again though! :(