Do the Spanish expect the same formality as the French do when one starts a conversation?

what other way is it to start a conversation?
It is improper to address an adult informally in Spanish.

It is improper to address an adult informally in Spanish.

What does that mean? Is it simply the equivalent of the French tu/vous issue, or is it something more?

That is correct
Usted/Tu.
Tu is when talking to friends or children not complete strangers.
Buenos Dias Senor/a instead of Hey!

While the Spanish are not as polite as the French(they are amused that Brits/Americans always say thank you to everyone), when you address an adult you don't know, the Usted form is used. Young people are much less formal and many use the tu forms.

But as with any culture, saying Hola or Buenos ___ is always appreciated. In America I hope you wouldn't address a hotel clerk with "Hey you!" :)

Hi guys, Castillano speaker here, both ways are actually fine, of course it's more polite if you say "buenos dias" before, as in any language. For example, you can address a hotel concierge in Spain you can say the "good day" before "I am looking for a room" or you can just cut right to "excuse me, I am looking for a room", formality is not so ingrained as in French, you won't be looked at badly if you fail to give a formal greeting in Spain.

Now the interesting part is that Castillano is a global language, so there is varying degrees of tolerance for formality vs. informality depending on if you are in Cuba or Argentina. Interestingly, in Mexico I find they speak Castillano more in the old style with more formality, and use some words that would be considered outdated in Spain, like "Carro" (literally "Cart") for car instead of "Coche", which is favored in Spain.

In school here they teach English speakers learning Spanish the old school rules from the start.

One has to love the different Spanish words used in different countries, or within the same country. e.g., aseo, retrete, bano, sevicio, toilet. I’m sure there are nuance differences, but I’ve seen all of them used in Spain. Argentina uses a number of verbs not used in Spain. Makes traveling more interesting.

Buenos, these replies have been very helpful. Gracias to each of you who replied!

Is Buenos dias, senor/senora an appropriate conversation opener (assuming it's not night)?

And is hola too informal to be used by a tourist conversing, say, with tourist industry workers? Is it a friendly "hi" or is it more like "hey you"?

Unless you are checking in at the Ritz or fine dining, I've found hola is fine-especially when they know you aren't a native speaker.

IMO, nowadays Spain is a lot less formal than other Spanish countries-except for that dreaded vosotros form. In bars, I've heard Spanish customers say, "Me pone una caña" -which literally mean "put to me a small beer"-instead of the more formal "Quisiera una caña"- I would like a small beer. However, always err on the side of caution.

Me pone una caña"

But that customer used the formal version of poner addressing the bartender and not [tu] me pones.

In most cases in Spain, one does not really use the formal "señor" "señora" on a day to day basis, "Hola" or simply "buenas" are common greetings. As for beer "me pones una caña" or simply "una caña" suffices. In Catalan, we can say "bon dia" as a greeting or "adéu" for a goodbye. In Barcelona, we can switch between Catalan and Castellano multiple times a day, depending with who we talk to.

Personally I'd stick to "hola" which is perfectly polite and easy to pronounce. I can't think of any interaction a tourist is likely to have where it wouldn't be fine (unless you get arrested, perhaps). It's the same word in Catalan too, I think, which saves learning another word when up there (it is different in Basque though, if you're going there). It also avoids any question of whether now is "tardes" or "naches" if you use "buenas ....".

If you do say "buenos dias", then I'd not add senor nor, especially, senora, which can be a bit of a cultural minefield (what do you call a waitress who looks 18? Senora sounds silly unless she is obviously in charge, but many younger woman consider senorita old-fashioned, even offensive).

Buenos dias just means good day and isn't especially formal. That would be "¿como esta?", which the equivalent of the British greeting "how do you do?" and is formal, and dying out.

And in answer to your original question, I'd say Spaniards, at least the Southern ones, are generally much more laid back and less uptight than the French, at least the Paris ones.

Apart from the direct conversation starting, "Hola" and "Buenos Dias/Tardes" are usually used when entering a store or bar. And not just for the help but to the other clients/customers. This morning, for example, as I was entering a cafe to get a coffee, the guy standing outside the door smoking his cigarette greeted me with an "Hola". I gave him an "Hola" and entered. Going past him on the way out, "Adios" "Adios". Never seen him before.

The same thing, many times when someone enters a store, they will greet the other customers, and when some one leaves they will say good bye to the other people in the store.

When you are eating, people will also say "Buen provecho" (bon appetit) as they walk past your table.

In Basque "hola" is "kaixo" (Kie-show)

Nick, I encountered the same situation you allude to, in Paris, where I entered a store, saw the clerk behind the counter from 20 feet away, and when I greeted her with "Bonjour madame" she was obviously not pleased, I then approached the counter and when I was closer saw she was younger than I thought, I then tried to make up for my initial faux pas and said "Bonjour mademoiselle", she smiled a bit then, but I could tell she was a bit offended by my initial faux pas.

So I understand what you mean when you say that senora/senorita is "a bit of a cultural minefield"!

These replies have been very helpful.
And I found the replies from native speakers to be especially helpful.
So thanks everyone for your replies to my question. I have found that the language books and websites don't seem to cover the "formality/informality/open conversation with"details, which to me seem important for a traveler to be aware of.

... I am sure you know that in "Spain" there are different cultures (and languages) and each one has its own ways, right?

In Catalan language for example, it's customary to say "bon dia" (good morning) rather than "hola". The later is far too informal and you'd most likely use it in a different scenario (not when entering a store, for example). Having said that, some local people also use "hola", however this greeting denotes some degree of familiarity with the other person, which is not normally the case for a visitor coming on holiday. I would say that Catalan is in between Spanish and French when it comes to formality in the manners. The term for "good bye" better illustrates this, in Catalan you'd formally say "Adeu ciau", you can also use "adeu" if you want to be a bit more informal, and if you have a degree of familiarity with the other person sometimes you'd shorten it to just "deu".

Obviously, as in many other languages, not all native speakers have the same manners nor the same understanding of "proper" talk, so you can probably find all sorts of responses.

But again, you won't be frown upon if you break protocol moreover noticing a foreign accent.

What I can tell you is that if you visit Barcelona or any other part of Catalonia, you'll put smiles on a lot of people's faces if you try some Catalan words/sentences even if it's just to break the ice and then continue the conversation in English or in Spanish as this is seen by native-speakers as a great sign of respect towards a minority language such as Catalan (spoken "just" by 10 million people in Spain, France, Andorra and Italy). Should you want to try.... http://wikitravel.org/en/Catalan_phrasebook

Enric, we will be in Barcelona and so your reply was especially helpful in providing the Catalan greetings phrases, which we will make sure we switch to when leaving Seville and going to Barcelona.
And I'm downloading to my phone the Catalan phrasebook that you thoughtfully provided the link to.
Gracias.

Kent, it would be "gracies" in Catalan as opposed to "gracias" in Spanish, I know very similar ;)

It's about 50/50 for Catalan and Spanish usage in Barcelona, it's a pretty cosmopolitan city after all, you may just end up talking to a south American immigrant who does not speak much Catalan. You will find it more widely spoken in the countryside or smaller towns like Girona.

Gracies is another word I'm now adding to my Catalan phrase book!

Kent... this one is easy to remember :))...as a general rule plurals in Catalan end in "-es" (ie. planta > plantes, cotxe > cotxes, rambla > rambles...)