for my Tier 1 to Low Tier 5 ships I pick a theme and run with it. For Instance
Male Catian Tac: WWII Battleship names
Male Grey Sci: US Civil War Battle names
Female Human Eng: Robotech/Macross Theme
Male Human Eng: Arthurian Legendary weapon names in Welsh
Male Alien Sci: Apollo 11 related names
Female Alien Sci: Babylon 5 Theme
Then I get to the Tier 5+ ships and they all turn out to be Yamato, Mushashi, and Shinano
I kept glancing at your avatar as I read this. I kept thinking, "He has to have Starblazers theme" and then low and behold your T5 did just that.
Oddly enough, I LOVED my Stargazer/Cheyenne-Class. I opted for U.S.S. Crazy Horse, in keeping with the "Famous historical generals" motif. I've gotten more compliments on that ship than any other I've had before or since. I only wish we could get a Brass Plaque with a brief bio that we could display on our bridge.
My Eng has ships named for Women of note, explorers, and warriors. Hypathia, Barbara Hillary, Xenobia, Jeanne d'Arc, Mae Jemison...
My original character, a Tac, had Thor based names...
My Sci has astronomers and astrophysicist names Ulugh Beg, Edwin Hubble, Tycho Brahe....
I generally just leave it at whatever the game auto-gave me. However I did rename a couple
Nova Class: USS Feynman
Intrepid Class: USS Edison (actually this one was auto-given, but it was well suited)
Intrepid Retrofit (and now also Refit): USS Wright (another auto-given that I liked)
While I was RA I goofed off with my ship names as I didn't really like any of the free ships available to me. So I had the USS Nagasaki & the USS Chernobyl.
USS Huntsville (Town of my birth)
USS Saratoga (Because, dammit, it's time for it to be on the winning team)
USS A Fortiori (Latin for "argument from stronger reason)
IKS [Insert Famous Canon Klingon Name] (Because I don't care.