Strange, I've only ever been able to build frigates. I have 5 cities and 8 or 10 shipyards. Some kind of bug then?
You should be able to build Destroyers and Cruisers as soon as you've finished your first Spire City. They require no special unlocks, just the presence of Shipyards.
Click on one of the Shipyards, and you'll see a full set of tabs. By default, the "FF" tab, to produce Frigates, is selected. Clicking on any other tab ("DD", "CA", etc) will switch to that class of ship.
Just make sure you're at a Shipyard, and not the original Refugee Outpost - that can only produce Frigates, no matter what you've unlocked.
See the picture below.
This is a Shipyard (upper right) and the Shipyard's production window. The FF tab is highlighted, but you can see the other tabs. Click on DD for Destroyers, CA for Cruisers, BB for Battleships, DN for Dreadnaughts, and COL for Spire Colony Ships.