I always assumed they built ships in batches, and ships in the same batch would have similar names (so one batch will be named after capitals, then the next after countries, a third after states/provinces etc)
A couple of ideas:
Surya <- I've heard somewhere that its Sanskrit for "Sun"
Zedong <- I've always felt the federation has a slight communist feel to it, so it might work, and it would be nice to see some famous non-western names and themes in the game (the federation is meant to be a worldwide alliance after all, right?).
Liberator
Endearing
Protector
Patreaus <- American General
Abrams <- American General
Harbhajan <- Famous Sikh warrior
Indefatigable <- Old British ship name. Means "untiring".
Highlander <- old scottish warriors (and some crazy dude with a sword

)
Immortal <- Ancient Persian elites
Sparta
Spartan
Leonidas
Samurai
Shinto
Men-Shen <- An ancient Chinese protective demon
Oni <- Japanese word for demon
Tengu <- Type of Japanese demon
Kitsune <- Another type of Japan demon
Shogun <- would be great for a capital ship
Katana <- Japanese sword
Wakizashi <- another japanese sword
Tanto <- ...and another...
Komodo <- big Aisian lizard thing
Guess what inspired these ones

...
Autumn
Amber
Dawn
Warthog
Scorpion
Mongoose
Ghost
Wraith
Scarab
A couple of ideas from Freespace 2, a game i'm a big fan of;
Myrmidon
Hercules
Pegasus
Perseus
Erinyes
Deimos
Fenris
Leviathan
Aeolus
Orion
Hecate
Arcadia
Watchdog
Cerberus
Aslator
Poseidon
Chronos
Triton
Aquitaine
Galatea
Bastion
Carthage
Rapier
Explorer
Terra
Xerxes
Talos
Hope those help ya