Will I have to verify my account or the person sending me money in order to withdraw or receive anything?
No. You just give them your Bitcoin address and that's it. If you send the coins
directly to Paymium though, they may need proof of origin, as they have said.
You may want to set up a "middleman" wallet so you don't risk losing the funds. Set up an Electrum wallet or something similar (a wallet you fully control, no verifications necessary, but no cash out option), have the person send the coins to an address in that wallet, then send an amount just below their proof of origin threshold to your Paymium wallet for withdrawal.
If we're talking about a massive amount, you shouldn't be sending it all to an exchange anyway because they could lock it up. If I were you, I'd focus on receiving and securing the coins first before worrying about converting it to cash.