How important is the size of the public key (for a given security level)?
Larger public keys (in the same scheme) lead to


larger signatures
larger certificates
slower signature computation
much slower key generation


All of these might be a problem, especially for embedded devices, as you already mentioned.
As for your last question: Yes, there are a lot of protocols which transfer a public key, usually in the form of a (X.509) certificate. A TLS handshake is just the most prominent example.