I'm just looking for a bit of advice to get started.
I have 81 LEDs to control individually from a sketch. These will be RGB LEDs and as bright as I can afford.
I'd recommend 10-12mm LEDs for brightness. Clear plastic if you want to shine them on something to light it up, diffused if you're going to be looking directly at them.
Go on eBay and look for "LED pixels", although I'm not sure they do them in clear plastic.
If you need clear plastic you can make your own:
Just add wire.
(nb. auctions picked at random)
You could also get a WS2811 LED strip and chop it up into individual LEDs. That would be cheaper but not so bright (although still much brighter than multiplexing).
You could drive those with any Arduino, even a Tiny85.
Can anyone recommend a multiplexing approach to start me off? To my understanding, the selection of four-pin RGB LEDs may complicated things. If this makes the task impossible I would consider switching to two-pin LEDs.
Four pins doesn't make a difference. Buying common-cathode instead of common anode would
(common cathode=bad, mmmkay).
Muliplexing? Far more difficult for very little gain (and a decrease in brightness)