Do I need pull-downs for the level shifter inputs for when the GPIOs aren't being driven?
Yes, I can almost guarantee this is the root cause for your problem. When you're not driving the GPIOs the inputs to the CD4504B are left floating, and it's always trouble to leave digital inputs floating. (By the way, why would you ever not drive the GPIOs here...?)
An easy way to verify this is truly the root cause: since you're on a perfboard and your voltages are nice and low, you can simply touch your fingers to the Ain/Bin/Cin/Din wires of the CD4054B. (Make sure you are following good ESD practices before you do this of course!) If your fingers have a significant influence -- if your fingers cause problems when the LEDs are otherwise quiet, or your fingers quiet the LEDs when there is otherwise a problem -- then it's these four wires that are the problem.
Add some decently high (10k or even 100k) resistors to these lines. Pull-down or pull-up is fine -- favor whatever is the "idle" state for those lines. The important thing is that the inputs are not allowed to float to some invalid state or, worse yet, oscillate.