I would like to start a new civi installation on WP to keep around 1000 contact records. What is the best option, Shared hosting vs VPS? Pros & cons? Any recommended hosting provider? Thanks
Shared hosting can work well, but use one that specifically supports CiviCRM.
Typically VPS offers more resources (RAM, CPU etc) but at a higher price. VPS's are not all the same: on unmanaged ones you need to do more sysadmin work but have more flexibility; on managed ones there are more restrictions but more of the work is done for you.
Good shared hosting gives you flexibility while taking care of all the basics.
Have you considered CiviCRM's own Spark offering?
I've had good experiences with shared hosting on CiviHosting