I dunno what's possible for you to do (I believe you can do anything though) and I dunno how much you're willing to do, so i'll just brain dump everything that'd be useful for us, in order of how useful I think it'd be. Ideally speaking, much of this would be character specific; I understand that because there's so many characters, that would be a lot of work, so if you were to decide to do that, prioritizing top tiers first would be a good idea. These could be implemented as CPU settings in training mode, or just as CPU behaviors in general.
Semi random DI and SDI CPUs with random teching
Don't want the DI to be totally random, as most points on the stick do not produce unique or meaningful DI inputs. Random cardinal inputs for DI (Up, left, down, right, and the diagonal directions) plus half diagonals (ie 22.5 degrees away from vertical or horizontal) would probably be more than enough. SDI inputs could be randomized between 0-3 inputs, each of them a diagonal input in the same general direction (ie never opposing diagonal inputs because that would produce no effect- players tend to hit quarter circle SDI fairly consistently in PM which is two diagonal inputs in adjacent quadrants, ie downleft+upleft or upright+upleft).
Random teching is pretty self explanatory. Favoring tech in place slightly might be ideal since that's generally the hardest option to cover.
Semi random actions on wakeup and actions after hitstun
CPUs could choose between their fastest options for avoiding punishes after their tech options. For most characters, this is options between dash (either direction), jab (any mix-up of them), shield, spotdodge, CC, fast tilts/smashes (think ROB's dsmash or spacie utilt), shine (if they have it), quick up-bs (if they have one, especially if it's invincible).
Same goes for actions after getting combo'd. After their last frame of hitstun, CPUs could jump out (in any direction, favoring extremes/neutral), fall down with a quick aerial, jump+aerial, use a stalling special (like marth's side-b or shine) or any special that shifts momentum (ROB side-b), or simply mashing out of tumble and doing nothing. Delaying any of these options slightly also has value.
CC options
It's kind of an extension of DI/SDI, but it's important enough that it should be a separate mechanic. This might be the hardest to implement effectively, but only because it's hard to know where to stop. As you approach top level, players option select more and more actions to be holding down while they're occurring. Eventually you could see players even going so far as to hold down on the cstick at (almost) all times, in order to get ASDI down during dash dances. Additionally, deciding when to CC and when to simply DI for survival/DI for a combo is hard to pin down, too. You probably *could* tell the CPU to use a rough approximation of when the move can't be ASDI'd down into the ground anymore based on knockback and knockback angle, but that's even remotely close to how humans do it- humans have reaction time, so the ideal scenario is one where the CPUs account for approach options that punish you for CCing (which changes based on percent) and approach options punish you for doing something other than CCing, and determine which is more threatening. The easiest way to implement this might simply be to give the CPUs a decreasing chance based as percent increases to either a: CC the move they get hit by or b: DI the move as normal.
OoS options
This one seems hard to implement effectively, as you'd want the CPU to try to punish the player for doing unsafe things while not trying to punish them for safe things, and defining safe requires evaluation of both spacing and frame advantage. But if you could define to the CPU what is safe and unsafe, you could have them punish the player with shield grabs, quick aerials OoS, up-b OoS, shine OoS, upsmash OoS, or wavedash->any of these things. You could also have CPUs simply try to escape shield pressure, with rolls, wavedashes, and fullhops OoS.
Projectile spam CPUs
Each character has unique options for repeated projectiles so this would likely be a lot of work. There's land cancels, airdodge cancels, glide tosses, simpler projectiles that simply end quickest via IASA. This'd be great for players struggling to learn powershielding and projectile clanking, though.
Additional overlay ideas
Overlay on idle has already been mentioned, but overlay on ledge hold idle shouldn't be overlooked- it'll help people practice their frame-tight ledge options and maximize ledge invincibility. Shield stun overlay would be great too, so it's easier to develop an understanding of how much shieldstun moves have.
I'll add more ideas as I think of them.
Edit: Added CC options