I don't think they need a new unit between Frigates and Battleships. They just need to have Battleships unlock at an earlier Tech. Carriers obsoleted Battleships, so they shouldn't be unlocked at the same Tech.
That would work, too. Perhaps a new tech near flight and railroads, where both the battleship and destroyer unlock.