Firstly, PVP dedicated area in game. An asset anyone can fly to in game and sign up for a CQC type battle. Different tiers of skill and ship class to keep it fair, and other players could park and spectate using a free cam or on big display screens for a more social experience. Unique rewards for performing well, and even titles for champions in each class. Use default rental ships or bring your own, make accessible for beginners but also give a dedicated location for experienced players to test themselves and their ships.
Missions that task players with hunting down other players. You get your name on the target list through different reasons; accumulating massive bounties, making a faction hostile for various reasons etc. Maybe tie them to other missions. Where you accept a trade mission and "hostile ships may be sent against you" how about that hostile ship is an actual player who recieved an inbox mission to stop you?
Maybe you get a mission saying "A wanted criminal has been spotted en route to (insert tourist destination) as a passenger on the notorious cmdr (insert cmdr name) ship, the (insert ship name and type). Last seen in (location), we need you to ensure that the wanted criminal does not make it to (destination). Leave no witnesses.
Make these shareable missions as well, so a wing of people could team up to hunt down someone who might be in a better ship or of a higher skill level and get paid for it. This will encourage tactics and team work, whilst at the same time giving an added level of risk that NPC ships don't always provide.
