Well, all the quantum stuff is more marketing than anything else. I think it's snake-oil. All the big VPN services use encyption that's itself unbreakable.
And as far as I know NATO is a military alliance. Their main job is to do military operations, like navy maneuvers and assure no member country gets attacked. I don't think they do much domestic surveillance of citizens, as they're not an intelligence agency.
As far as I know all of those three services are reputable.
Sure, researching these algorithms is a valid concern. Just advertising is misleading. Since there are no quantum computers around which would be big and reliable enough to do these calculations. And as far as I know we're not even sure if we can buld them at all, or in what timeframe. So they're advertising to protect against something that doesn't exist. I think that should be factored in when comparing services.
And by the way: I think it's mainly the key exchange that is affected. I guess the tunnels are protected with symmetric cryptography? And quantum isn't really an issue for most symmetric cryptography algorithms.
And yes, the handshake is made over an assymetric cipher, and then you use a symmetric one because they (this is not true for all symmetric algorithms out there, but the ones used in ssh etc. are) are both way faster and actually safe against quantum algorithms.