I think you can do this! I've built two "big" DJ lighting effects.
Use your imagination & creativity and program-in some randomness & variability to keep things interesting. Any single effect can get boring after a minute or two. Just for example, maybe make the red LED respond to the bass for awhile, then make the green LED respond to the bass. Or, use RGB LEDs an change the colors around.
I'm not sure if "standard" LEDs will be bright enough when "dotted around the stage". One of my projects is an 8-foot "VU Meter" and standard "high brightness" LEDs are bright enough with 24 LEDs in a row.
I've never used the MSGEQ7, but it's a good-easy way to get the frequency & volume information into the Arduino.
I haven't used the TLC5940 either, but I've used a similar Maxim chip. The advantage of these serially controlled chips is that you can daisychain them to drive almost as many LEDs as you wish with only 3 control lines. (I have six 8-channel LED drivers for 24 LEDs on each left & right meter.)
If you need more light, you'll need special drivers for "high power" (1W or more) LEDs, or solid state relays for incandescent lights. The good news is, if you build the thing and then want more light, you can use the same basic Arduino setup and software.
Just to give you some ideas, here's what I've done:
I don't use any frequency detection for my effects. I just use loudness and some crude beat detection. I keep a 20-second moving average of the loudness to auto-calibrate the sensitivity. I also automatically switch between the 5V and 1.1V ADC references depending on loudness. This works well with line-level (Aux) signals and I don't have a manual sensitivity control. (Whenever it switches between the 1.1V & 5V references the data in the moving-average array has to be scaled up or down.)
My VU Meter effect randomly reverses (where louder is down) and it randomly switches between the normal bar-graph mode and dot-mode. In the dot-mode, the number of dots (LEDs) representing the loudness is randomly selected. Besides the VU meter effect, there are 6 more chasing, sequencing, blinking, flickering effects with all kinds of random (and non-random) patterns. I consider this giant VU meter to be a "special effect", and even with all the various modes I think it can get boring.
I also built a 4-channel AC lighting controller. It has the same basic modes as the VU meter effect, except there are 4-channels instead of 24, and it's mono instead of stereo. I can plug-in 8 colored 100-Watt flood lamps (4-colors), or in another configuration I plug-in 16 30-Watt white floods that I arrange in various configurations (in a straight line, in a square with 4 lamps on a side, etc.) With the colored floods, I consider this a "main effect" that lights-up the whole dance floor and it can run all night without getting too boring.