Of course, you may call it 'лестница' when you came from outside as well.
In this case you must reach at least that part of 'the space between' that contains a staircase (and elevators) - though you shouldn't necessary stand on the stairs - it's formal name is лестничная клетка.
Я зайду в подъезд и подожду тебя на лестнице.
As I understand, most probably these refer to 'space between the doors of apartmens and the entrance to the building', which in a building with more that one storey contains a staircase?
mainly this space has no proper name - though the way people call it depends on particular city: for example what in St.-Peterburg is called парадное/парадная (a substantivated adjective. I'm not sure on the etymology, maybe it is from 'парадный' in the sense of 'official, main' [entrance]) is 'подъезд' in Moscow.
The proper meaning of 'подъезд' - literally 'something you may ride to' - is entrance, now usually applied to the buildings with living appartments. Either denotes the construction of entrance itself (roof, 2 or 3 doors to keep warm air), or as in 'у подъезда' - location, or, when (usually) there are many of them -
4-й подъезд (4th entrance).
Я живу в пятом подъезде (as part of the address - here it denotes the whole collection of appartments accessed by 5th entrance, or part of the building associated with it. Cf. всем подъездом by Leonid).
In may also mean the 'space behind the entrance' when reached from the outside!
'Лестница' is just 'the staircase'
But when you are in appartments, it may mean the same 'space behind the door'
выйти на лестницу покурить.
Человек, который вышел на лестницу покурить can meet another man, который зашел в подъед погреться.
Лесница is just the stairs, steps.
Подъезд includes the space before the entrance door on the street, the staircase, the elevator, the flats.
This word also has another meaning:
Мы вышли на улицу всем подъездом. This means that all people living in this "подъезд" went on the street.
1. Подъезд it is most oftenly the place where the spiral stairs are situated or a place where you can find an elevator.
2. Лестница it is a thing you are going by your feets.