Either IMAP or Exchange, but Exchange would have to be set up for that.
With IMAP, the emails are kept locally, so if you delete the ones on the PC, the ones on the phone are still there.
It sounds as if you are running POP3 (or Exchange set to run like POP3).
With POP3, you can set the email client to not delete the emails from the server when you read them, but when you delete them, you're deleting them from the server (not "deleting them from one deletes them from the other" - if they're deleted from the server, the other one won't see them there, which is what you're seeing with POP3 - the client shows you what's on the server). You can't delete them "but not from the server" - POP3 only does what it does, on the server. IMAP does what it does in each client - deleting in the PC doesn't delete from the phone or vice versa.