Do search on Gartner website to identify best HR System providers. Few top providers like, Workday, Peoplesoft have some minimum headcount requirement of 1000 and above.
There are many other players to name, Cornerstone, Ramco, Adrenaline and so on.
HR System Costing:
The costing is based on number of users (licence cost per user)
And implementation cost.
Also, at times you may opt for customization in the product to meet your organization needs this will eat some budget.
Hence, you have to consider these and propose a budget for HR system.
Please bear in mind, once you have the system, the system should be used by all 500 employees for PMS and for any other requirements, only then the technology will reach to all employees.
Also, have clear structure of your company and HR processes before you start the project.
If you don't have HR processes, please write the policy and processes first before you kick start the project.