Heres an idea: have pregenerated lists of names that ships are automatically assigned rather than the rather bland names they currently have. Allow players to specify or modify their own. Additionally, the names could be meant for certain sizes or types of ships, so that a Dreadnaught is going to have a more interesting and unique name than a tiny fighter.
This'd mean that instead of, say, Frigate M1-5 294, I might get something like "TESS Declaration". This would also add a ton of flavour to the AI ships, if lists were created for them as well.