THANKS for the input, dknguyen.
I hadn't even looked at the dsPICs, but will now as FFT might not be as complicated as I earlier thought (by doing it in software).
256 bins is far more than I need as I plan to assign the entire frequency band (30Hz-7000Hz) to 10-20 frequency channels, with each channel assigned to either a unique color (via 8x8 RGB LED matrix) and/or display patterns.
I expect to update the color/display pattern between 5 and 40 times per second, depending on type of music and desired visual display.