My take on this is time-dependent.
For the first half of the Star Trek pseudofuture, starship would indeed be something like battleship today: there'd be star corvettes, star frigates, star cruisers (canon from "Peak Performance", and probably separate from the cruisers Scotty mentions in "Relics" or from the cruiser Aurora
of "Way to Eden" fame), and then starships. NX-01 would be the first ever star vessel from Earth to warrant the designation, but every alien design from the very smallest up would be a starship in comparison.
Whether Kirk's ship would be a star cruiser and
a starship simultaneously, or one thing or the other at different points of her history, the reader can decide. Perhaps heavy star cruiser was the same thing as starship as there was nothing bigger in service to compete for the term?
But after Kirk's days, basically every vessel in Starfleet service would become capable enough to warrant the designation starship, and only certain diehard enthusiasts like Worf or the Zakdorn strategist Kolrami would insist on distinctions like "(star) frigate" and "star cruiser". Of course, there'd still be ships that are more equal than others, and now "star cruiser" would be small potatoes compared with the "real starships", now typically from the explorer category. Again, explorer would be an analogy to today's (yesterday's, really) battleship in defining a very specific combination of capabilities and size - "explorer" would no more mean a generic vessel that explores than "battleship" means a generic vessel that battles.
As for the Ferengi exclamation, surely one would need further defining after saying "Federation vessel", because the Federation no doubt operates garbage scows and cometary trawlers in addition to the combat vessels of Starfleet...