Wordpress portfolio - two level sorting?

I'm setting up a Wordpress page for a client and they have requested an unusual way of sorting the portfolio page. They do 3 different kind of works and would like the portfolio to display clients AND what kind of work they did for that client. For example:

CLIENT 1
- Category 1
- Category 2
- Category 3

CLIENT 2
- Category 1
- Category 2
- Category 3

CLIENT 3 - Category 2
- Category 3

The goal is to have the Clients visible all the time, no matter how you sort the portfolio (the grey blocks in the attached image is supposed to illustrate some kind of background image with logo etc). So if you filter on Category 1, only the blocks that displays Category 2 and 3 is hidden. If you click on the Category 1-block for Client 1, it goes to portfolio item page. The Category 1-block for Client 2 goes to another portfolio item page.

Is this even possible to do in Wordpress with the portfolio function!? I'm pretty used to building websites in Wordpress, but I can't wrap my head around this problem. Been thinking about using parent categories and subcategories, but still not sure how to get it to function the way the client would like. Or can I use the tags function somehow? Maybe there is a plugin that can help me? It must be easy for themselves to update the portfolio with new clients.

Any input would be MUCH appreciated! Thanks in advance!

via Chebli Mohamed