Is it possible to derive an eosio account name with just a Public Key? I am thinking this might be impossible because a single public key can own many accounts, so I don't they have any correlation to each other.
Yes, it is possible.
cleos you can just run this command:
cleos --url https://api1.eosdublin.io get accounts <EOS public key>
This will give you a list of account names associated to that public key.
Otherwise, you can simply search the public key in https://eosflare.io/ or any other EOS block explorer.
Very possible. EOS Authority will show you what your name is along with many other interesting tidbits with just your public key. Your name was set at the time your registered your tokens to a random 12 character ID.