Is there a Photoshop or Illustrator action/plug-in for adding complexity?

[ChickPea]

If you're working with vector (since you mentioned Illustrator) you might consider the fractalize extension in Inkscape...

Export an SVG from Illustrator and open in Inkscape
If you're working with a raster file, you can still use Inkscape, but you'd need to export a PNG from Photoshop, import this into Inkscape, then run Path > Trace Bitmap on to create a vector object.
Then go to Extensions > Modify Path > Fractalize
Play about with the numbers to see what suits you (turn on the Live preview)
After running the function, there will be a lot of nodes. If you want reduce them, try hitting Ctrl + L (Simplify) once or twice.
You can export a high-res PNG if you want a raster file to open again in Photoshop, or use File > Save As and select 'Optimised SVG' from the drop down box of file types. You should be able to open this in Illustrator without any problems (I hope!)

I don't have PS or Illustrator so can't offer any advice for those programs. Sorry.

[gkoch1]

I'll check out Fractalize. Thank you. I don't know Inkscape, but I'm willing to learn if it gives me the output I seek. Much appreciated!