Don & Doña

So if we were introduced (assuming not by first names only, and that we are the same class), you would be -

Don Smith or Señor Smith, depending on our relative ages?

And I would be Doña Jones or Señora Jones?

No I take it back. Señor, Señora etc. are used in introductions where last names are used. Don and Doña are only used with first names.

So you would be Don Steve (sounds odd to these American ears) and I'd be Doña Betty*.

* Not our real names. At least, I don't think you're named Steve.

Pitter is right.

You could say Don Manuel and Doña Isabel...

But Señor and Señora Philbis

Gracias, Don Francis.

De nada, Doña Jespah.

Now there ya go. Asi es...

Recuerdo un poco de Español. Un poquito!

Colombians are famous for being so formal!
This sound like 1940's Mexico (or the odd-sounding and wildly popular in South America 1970's TV show "El Chavo").

Here, if you call "niña" to any cleaning woman who's not at least 30 years younger than you, she takes it as an insult.

Don is used for respect, so it must be given back (and it's used very seldom). Señor(a) is used way more often.
The only person I call Doña is my mother-in-law; thus, she gives me the Don (but she sometimes forgets ). We both use the formal "usted", not the informal "tú", even when we joke.
Last year I had some builders remodelling my house. They called me "Don F."; in return, I gave the "Don J," to their head (the father, they were a family) and "maestro" to the others.

I have noted here that "tu" seems to be used only amongst the educated class. The rest of the world uses "usted" for everybody except small children and then only sometimes.

That's a typical Colombian trait.

Here it's strictly a confidence thing. If confidence has been built, then you use the "tú"; with a waiter, a passerby, a bank teller you don't know by first name, you use "usted".

Lately the use of "tú" is getting to be way too common.
A similar thing happened in Argentina during the Dictatorship: now everyone uses "vos".