I've decided to go with the 8x8 matrix. I've ordered 2 of these now to see how it works. They are bi-colour (red and green) but I will only be using the red part.
I'll update the thread with my progress, if anyone is still interested.
I might even make it modular and design a small PCB that holds one matrix and one MAX7219. ;D