All of mine fit into three categories.
The character's real name (or some variation on it)
Officer Nikolai (Praetorian cop, Kin/WP Brute)
Kethariel Veradenia (Elf, Dark/Katana Tanker)
Something that I find especially fitting, often a single word
Nya (Catgirl, Savage/Nin Stalker)
Revenant Fist (MMA fighter who died and came back, StJ/WP Scrapper)
Wrecking Belle (SS/Invuln Brute)
Stateless (Praetorian resistance, Plant/Rad Controller)
An anime or video game reference that I hope is subtle enough to not get generic'd
Spirit Detective (Beam/NRG Blaster)
Sunlight Overdrive (Peacebringer)
Burning Crusader (MA/Fire Scrapper)
Flying Shadow (BS/Bio Stalker)
Shell Bullet (Huntsman)
Phantom Blood (Vampire, just holding the name atm until I can decide on powersets)
Star Outlaw (Space pirate, similar to above holding the name until I know what powersets to make)