Custom post type as a category, for another custom post type

I did the exact same thing (connecting projects & clients) using the Advanced Custom Fields plugin. I did this because my clients needed custom fields as well (logo, website URL).

I used the ‘Post object‘ field for my project page, which will create a dropdown of your clients.
Some editing of your template is required (to show your client info near a project), but the documentation on the plugin’s site is really good.