Best way to control 75 LEDs with Arduino
I would suggest going the matrix route with a driver like the MAX7219 you mentioned or maybe, if you wanted a lot more control, the TLC5951DAP, a TI LED driver meant for RGB leds that will give you 24 channels with a 12 bit resolution (4096 different steps of brightness for each channel). This will allow you to turn on each of the R, G, and B LEDs to different brightnesses to mix the colors to what you want.

You could use ribbon cable for the wiring to each of the LEDs (I'm assuming wiring is why you do not like the idea of the matrix) and have all of the cables plug into a controller board. For something like this, I would definitely recommend that you make a pcb for the controller because that's a lot of connections to try to do by hand. That's just what I would do though.

The STC2026 looks to be directly compatible with the STP16C596, so that's a perfectly good replacement if you want to use it. I would agree that controlling each LED individually will probably be cheaper and easier than trying to use some sort of MUX to have 2bits control which LED is on.

Hope that helps.