The conclusion from further discussion with players was: "Starship" is less inaccurate and rolls off the tongue better than "Capital Ship" and more newbie-friendly than "Frigate/Destroyer/Cruiser/Battleship"
Basically it's a broader range than can really be called "Capital Ships" (those frigates just don't fit the name), and using individual size-class names was also unpalatable to many (though happy-inducing to others).