We're getting a bit off topic here by complaining about the mechanics again, but okay.
The first power armour you encounter could, well, be found in higher level areas and hidden in low level areas behind advanced locks which requires lockpicking or hacking, so you could come back later when you have more skills.
The earliest and easiest way (relatively) to get it should've been through the Brotherhood of Steel, or through opening up the Castle armoury.
But if we're still aiming for spectacle, AAA style, you encounter the Prydwen once you leave Fort Hagen after meeting with Kellogg. A Vertibird arriving with the Prydwen would descend to attack a raider camp or something nearby, and would be scripted to be hit and crash within the camp.
You could talk the raiders into letting you get the armour and leave, or go with action, fighting your way in and recovering it before fighting your way out. It would be the first appearance of power armour and from then on power armour would begin spawning in hard to access locations throughout the wastes.
That would've given the larger crowd the cinematic action experience they want, and the power armour introduction stays balanced anyhow. Plus, pacifist methods! Though why you'd want to get the power armour while playing a pacifist is beyond me.