Where does one store 3rd-party Public Keys
From a security point of view, you can store the public key wherever you want, as by definition it is public. This doesn't hold for the private key, which has to be store securely, as the security depends on it. 
As pointed out by @fgrieu (in the comment below), the integrity of both public and private keys should be ensured. In other words, it should be ensured that no adversary can change the public keys. Therefore, you might consider also storing the public keys in a key store which should make it a lot harder for an adversary to tamper with it. 

From an efficiency point of view, it really depends on what platform you are using. Of course you can store the public keys also in a key store (as a key store most likely offers some other useful functions). However, you can also just store the public keys in a database or the file system. Regarding the encoding (storing them as plaintext strings, hex strings or any other encoding) it again depends on your platform. You might have a look at this link.