This article sheds light on some details.
There was an air defense base nearby. They raised the alarm before Gagarin landed. An officer announced "We are working on space now!" which made everyone excited. Then they started to watch the skies. First they saw the Vostok spacecraft, then the catapult chair descending on its own parachute. The third object descending they saw was Gagarin.
They immediately got a vehicle and arrived to the landing site. Indeed, the first people Gagarin saw were the wife of a forest keeper and her daughter. But when he saw the soldiers, he in accordance with the subordination, addressed the Major "Comrade Major! Senior Lieutenant Gagarin..." with a report. The Major interrupted him and said "What "Senior Lieutenant"? Major!" (the news about his flight and granting new rank was already aired when he was in space, but he himself did not know yet). Gagarin went on: "I feel good, have no injuries or traumas!".
He then asked to call Moscow, which indicates he did not call Moscow before the military arrived (and, surely he could not, intercity civil calls were a complicated and expensive thing at the time that definitely would require waiting at a telegraph office). He indeed made a call to Moscow, but from the military base headquarters.