First name, generally. Really depends on what they do or their profession, though. If I know they're a doctor, I use Dr. Lastname. If I know they're an attorney, I use Mr./Ms. Lastname. Those are the customs in their profession, so I try to work with that. Usually they immediately say to call them by their first name.
Everyone else, first name, with very few exceptions -- notably, senior partners who I do not have a repoire with, then I take the safe route and use Mr./Ms. until corrected to the first name. I know for a fact that none of them would mind if I didn't, but I also know they sign my raises, so I'm going to kiss a little bit of ass.
Use your judgment on what's most respectful. It's not like it's degrading oneself to be respectful to others, so you're not "lowering" yourself by addressing someone formally.
I also find it important to get names right. For a hard name, you get one freebie, but everyone else get it right. Don't transpose first and last names or mispronounce easy ones. If it's a name that has plausible alternate pronunciations, pronounce it one of the ways and then ask, or ask which it is at the outset. If it's a difficult last name, say it if you know you can get close and then ask for the correction. If it's really out there and you know you'll butcher it, apologize and ask for the correct pronunciation. There is nothing as fundamental as knowing someone's name and you should do your best to remember it after that one shot. So many people don't that it's almost impressive, when it should be a basic qualifier. I do think a bit less of someone who can't be bothered to learn my name, whether they're my superior or subordinate. It reflects a certain carelessness that you'll eventually see in their other work.
Sorry for the mini-rant.
Cliffs:
Names are important, know them and don't forget.
Address people however you see fit, as long as you know their name.