Joseph Stalin
Anna Kournikova
Vasili Zaitsev
Andrey Arshavin
Again, no patronymics here. These are first names + surnames.
In fact, it's all very simple. Every Russian person has:
1) a first name (the one parents give him or her at birth),
2) a patronymic (which is formed from the child's father's name)
and 3) a surname (which is the same for all members of the family).
You can easily see that 1) and 3) are the same as in any English speaking country. Patronymics can be viewed as middle names - though they are not random or names of choice. Patronymic is kind of a tribute to a child's father.
For example, if a child's father's name is Vladimir, the child's patronymic will be "Vladimirovich" for a boy and "Vladimirovna" for a girl, and can't be anything else. And every Russian will know upon meeting this person in the future that his or hers father was named Vladimir.
About most common usage:
Patronymics are used after first names only (NEVER after surnames). [Name + Patronymic] is a formal and polite way of addressing a person (a stranger, an older person, a boss, etc.). A full set [Name + Patronymic + Surname] is common in documents.
Friends or relatives usually use first names to address each other. That's it in a nutshell.