Coming up with stuff on the spot. It's how I got names like Danim, Bins, Vasil...

Sometimes I'll name them something that means something. For example, Terra and Celes are meant to contrast in almost every way, so I usually give them some kind of naming scheme that in (Jade/Ruby, Violet/Indigo, etc,)

Play through Chrono Trigger with Marle named Nadia, Frog named Glenn, Robo named R66-Y, Magus as Janus... it gets funny at points.