Unlike in other blockchains, a key pair does not automatically create an account. An account needs to be created separately, and the key pair shall be associated with permissions on that account.
To create an account, however, you need to store data associated with the account in the state of the blockchain (RAM). RAM costs resources, so someone has to pay for RAM, which is why each new account needs to have a creator that pays for the initial RAM costs.
Thus, to create an EOSIO account, there is a cost involved that someone has to pay.
At the moment, your options are to ask someone with an exiting account to create you an account with the public key you provide them, or use a service that does it for you (example). In the future, Block.one mentioned that they will create free accounts for the community.
So even if I generated a public/private key pair, I need to first "initialize" it? Isn't this problematic if sending coins to a completely new person as they wont have anything setup yet but only a public/private key?
Yes, generating a key pair is not enough to participate in the network--the keys won't be automatically associated with anything. For someone to send and receive transactions, they need to create an account first. This workflow follows quite a different design from what other popular blockchains offer, but it's more similar to mainstream applications where accounts have human-readable usernames and permission access.
The whitepaper has a section on accounts explaining the design decision.