Does the "grade" of power armor spawning depend on what level the char is when he/she finds it? T45, T60 and such?

Yes. There are a few "guaranteed" spawns, but they're only "guaranteed" if you meet or exceed the armor's spawn level.

For instance, there's a T-51b power armor near the old church. If you are at the level t-51s spawn at, it'll be there. If you are high enough to get T-60s to spawn, it will still be a T-51. If you are below the minimum level... it'll be a T-45.

It's effin' annoying, since the power armor is locked once that cell loads. Even if you're not otherwise near the power armor.