1. It is, indeed, a problem. In the USSR, everyone used "товарищ" (comrade) regardless of the person's gender and status, so things were simple. In modern Russia, we are back to "господин" / "госпожа", but these are often considered too formal.
"Господин" / "госпожа" are commonly used for high-rank politicians and business people. In the news, you can often hear things like "Господин А нанес визит...", "Господин Б провел переговоры..." etc.
In less formal situations, we generally use first name, or first name + surname, or first name + patronymic.
2. If you want to introduce your old friend, in most cases, the first name is enough: Это Андрей, мой друг. (If you introduce him to your colleagues or other friends.)
First name + surname sounds slightly more formal: Это Андрей Николаев, мой друг.
First name + patronymic is even more formal: Это Андрей Алексеевич, мой друг. (Generally used for people of mature age, maybe 40+.)
3. First name + surname is fine: Вы знаете Марию Петрову? Она училась с вами в одной школе.
Or, more colloquial: Ты знаешь Машу Петрову? Она училась с тобой в одной школе.